Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1912.01765 · Communications in Mathematical Sciences

Universal approximation of symmetric and anti-symmetric functions

Jiequn Han, Yingzhou Li, Lin Lin, Jianfeng Lu, Jiefu Zhang, Linfeng Zhang

Published Jan 1, 2022• 36 citations
arXivHTMLPDF

Abstract

We consider universal approximations of symmetric and anti-symmetric functions, which are important for applications in quantum physics, as well as other scientific and engineering computations. We give constructive approximations with explicit bounds on the number of parameters with respect to the dimension and the target accuracy $ε$. While the approximation still suffers from the curse of dimensionality, to the best of our knowledge, these are the first results in the literature with explicit error bounds for functions with symmetry or anti-symmetry constraints.

DOI
10.4310/cms.2022.v20.n5.a8

Related papers

On Representing (Anti)Symmetric Functions

Marcus Hütter

Permutation-invariant, -equivariant, and -covariant functions and anti-symmetric functions are important in quantum physics, computer vision, and other disciplines. Applications often require most or all of the following properties: (a) a large class of such functions can be approximated, e.g. all continuous function, (b) only the (anti)symmetric functions can be represented, (c) a fast algorithm for computing the approximation, (d) the representation itself is continuous or differentiable, (e) the architecture is suitable for learning the function from data. (Anti)symmetric neural networks have recently been developed and applied with great success. A few theoretical approximation results have been proven, but many questions are still open, especially for particles in more than one dimension and the anti-symmetric case, which this work focusses on. More concretely, we derive natural polynomial approximations in the symmetric case, and approximations based on a single generalized Slater determinant in the anti-symmetric case. Unlike some previous super-exponential and discontinuous approximations, these seem a more promising basis for future tighter bounds. We provide a complete and explicit universality proof of the Equivariant MultiLayer Perceptron, which implies universality of symmetric MLPs and the FermiNet.

arXiv:2007.15298•Jul 30, 2020•45 citations

Bi-Lipschitz Ansatz for Anti-Symmetric Functions

Nadav Dym, Jianfeng Lu, Matan Mizrachi

Motivated by applications to the simulation of quantum many-body systems by neural networks, researchers have suggested several models which are antisymmetric by construction, and can approximate all antisymmetric functions. However, these works either require very high computational complexity to attain universal approximation, or suffer from discontinuities. In this paper, we introduce two antisymmetric ansatzes which do not suffer from these disadvantages. The first is based on a bi-Lipschitz embedding with respect to a naturally defined metric. The second is a modular anti-symmetrizing projection framework based on the frame-averaging methodology. Both approaches yield continuous antisymmetric models which attain universal approximation guarantees with a polynomial complexity in problem size. Moreover, for both approaches, we obtain quantitative approximation results that bound the number of parameters required to approximate Lipschitz antisymmetric functions to a given accuracy $ε$. We also provide preliminary experimental evidence suggesting improved performance in learning antisymmetric functions.

arXiv:2503.04263•Mar 6, 2025•4 citations

Quantum Algorithms and Complexity for Certain Continuous and Related Discrete Problems

Kwas, Marek

The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.

•Jan 1, 2005•3 citations

Symmetric and anti-symmetric quantum functions

John Robert Burger

This paper introduces and analyzes symmetric and anti-symmetric quantum binary functions. Generally, such functions uniquely convert a given computational basis state into a different basis state, but with either a plus or a minus sign. Such functions may serve along with a constant function (in a Deutsch-Jozsa type of algorithm) to provide 2**n deterministic qubit combinations (for n qubits) instead of just one.

arXiv:cs/0304016•Apr 10, 2003•2 citations

Generalized Notions of Symmetry in Quantum Mechanics

Philip C. Argyres

I describe a set of useful generalizations of the idea of a symmetry of a physical system that have been discovered over the last 30 years and indicate a few simple examples where they are realized in physical systems.

WORLD SCIENTIFIC eBooks•Nov 1, 2022•0 citations

Continuous Symmetries and Approximate Quantum Error Correction

Philippe Faist, Sepehr Nezami, Victor V. Albert +4 more

Quantum error correction and symmetry arise in many areas of physics, including many-body systems, metrology in the presence of noise, fault-tolerant computation, and holographic quantum gravity. Here, we study the compatibility of these two important principles. If a logical quantum system is encoded into n physical subsystems, we say that the code is covariant with respect to a symmetry group G if a G transformation on the logical system can be realized by performing transformations on the individual subsystems. For a G-covariant code with G a continuous group, we derive a lower bound on the error-correction infidelity following erasure of a subsystem. This bound approaches zero when the number of subsystems nor the dimension d of each subsystem is large. We exhibit codes achieving approximately the same scaling of infidelity with n or d as the lower bound. Leveraging tools from representation theory, we prove an approximate version of the Eastin-Knill theorem for quantum computation: If a code admits a universal set of transversal gates and corrects erasure with fixed accuracy, then, for each logical qubit, we need a number of physical qubits per subsystem that is inversely proportional to the error parameter. We construct codes covariant with respect to the full logical unitary group, achieving good accuracy for large d (using random codes) or n (using codes based on W states). We systematically construct codes covariant with respect to general groups, obtaining natural generalizations of qubit codes to, for instance, oscillators and rotors. In the context of the AdS/CFT correspondence, our approach provides insight into how time evolution in the bulk corresponds to time evolution on the boundary without violating the Eastin-Knill theorem, and our five-rotor code can be stacked to form a covariant holographic code.

arXiv:1902.07714•Physical Review X•Oct 26, 2020•147 citations
We consider universal approximations of symmetric and anti-symmetric functions, which are important for applications in quantum physics, as well as other scientific and engineering computations. We give constructive approximations with explicit bounds on the number of parameters with respect to the dimension and the target accuracy εεε. While the approximation still suffers from the curse of dimensionality, to the best of our knowledge, these are the first results in the literature with explicit error bounds for functions with symmetry or anti-symmetry constraints.
Permutation-invariant, -equivariant, and -covariant functions and anti-symmetric functions are important in quantum physics, computer vision, and other disciplines. Applications often require most or all of the following properties: (a) a large class of such functions can be approximated, e.g. all continuous function, (b) only the (anti)symmetric functions can be represented, (c) a fast algorithm for computing the approximation, (d) the representation itself is continuous or differentiable, (e) the architecture is suitable for learning the function from data. (Anti)symmetric neural networks have recently been developed and applied with great success. A few theoretical approximation results have been proven, but many questions are still open, especially for particles in more than one dimension and the anti-symmetric case, which this work focusses on. More concretely, we derive natural polynomial approximations in the symmetric case, and approximations based on a single generalized Slater determinant in the anti-symmetric case. Unlike some previous super-exponential and discontinuous approximations, these seem a more promising basis for future tighter bounds. We provide a complete and explicit universality proof of the Equivariant MultiLayer Perceptron, which implies universality of symmetric MLPs and the FermiNet.
Motivated by applications to the simulation of quantum many-body systems by neural networks, researchers have suggested several models which are antisymmetric by construction, and can approximate all antisymmetric functions. However, these works either require very high computational complexity to attain universal approximation, or suffer from discontinuities. In this paper, we introduce two antisymmetric ansatzes which do not suffer from these disadvantages. The first is based on a bi-Lipschitz embedding with respect to a naturally defined metric. The second is a modular anti-symmetrizing projection framework based on the frame-averaging methodology. Both approaches yield continuous antisymmetric models which attain universal approximation guarantees with a polynomial complexity in problem size. Moreover, for both approaches, we obtain quantitative approximation results that bound the number of parameters required to approximate Lipschitz antisymmetric functions to a given accuracy εεε. We also provide preliminary experimental evidence suggesting improved performance in learning antisymmetric functions.
The thesis contains an analysis of two computational problems. The first problem is discrete quantum Boolean summation. This problem is a building block of quantum algorithms for many continuous problems, such as integration, approximation, differential equations and path integration. The second problem is continuous multivariate Feynman-Kac path integration, which is a special case of path integration. The quantum Boolean summation problem can be solved by the quantum summation (QS) algorithm of Brassard, Hí yer, Mosca and Tapp, which approximates the arithmetic mean of a Boolean function. We improve the error bound of Brassard et al. for the worst-probabilistic setting. Our error bound is sharp. We also present new sharp error bounds in the average-probabilistic and worst-average settings. Our average-probabilistic error bounds prove the optimality of the QS algorithm for a certain choice of its parameters. The study of the worst-average error shows that the QS algorithm is not optimal in this setting; we need to use a certain number of repetitions to regain its optimality. The multivariate Feynman-Kac path integration problem for smooth multivariate functions suffers from the provable curse of dimensionality in the worst-case deterministic setting, i.e., the minimal number of function evaluations needed to compute an approximation depends exponentially on the number of variables. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the minimal number of function evaluations and/or quantum queries required to compute an approximation depends only polynomially on the reciprocal of the desired accuracy and has a bound independent of the number of variables. The exponents of these polynomials are 2 in the randomized setting and 1 in the quantum setting. These exponents can be lowered at the expense of the dependence on the number of variables. Hence, the quantum setting yields exponential speedup over the worst-case deterministic setting, and quadratic speedup over the randomized setting.
Quantum error correction and symmetry arise in many areas of physics, including many-body systems, metrology in the presence of noise, fault-tolerant computation, and holographic quantum gravity. Here, we study the compatibility of these two important principles. If a logical quantum system is encoded into n physical subsystems, we say that the code is covariant with respect to a symmetry group G if a G transformation on the logical system can be realized by performing transformations on the individual subsystems. For a G-covariant code with G a continuous group, we derive a lower bound on the error-correction infidelity following erasure of a subsystem. This bound approaches zero when the number of subsystems nor the dimension d of each subsystem is large. We exhibit codes achieving approximately the same scaling of infidelity with n or d as the lower bound. Leveraging tools from representation theory, we prove an approximate version of the Eastin-Knill theorem for quantum computation: If a code admits a universal set of transversal gates and corrects erasure with fixed accuracy, then, for each logical qubit, we need a number of physical qubits per subsystem that is inversely proportional to the error parameter. We construct codes covariant with respect to the full logical unitary group, achieving good accuracy for large d (using random codes) or n (using codes based on W states). We systematically construct codes covariant with respect to general groups, obtaining natural generalizations of qubit codes to, for instance, oscillators and rotors. In the context of the AdS/CFT correspondence, our approach provides insight into how time evolution in the bulk corresponds to time evolution on the boundary without violating the Eastin-Knill theorem, and our five-rotor code can be stacked to form a covariant holographic code.