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:cs/0304016

Symmetric and anti-symmetric quantum functions

John Robert Burger

Published Apr 10, 2003• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.cs/0304016

Related papers

Novel Identification of Symmetric and Anti-Symmetric Quantum Functions

John Robert Burger

Procedures are given below to construct symmetric and anti-symmetric quantum functions. If hidden in an oracle, such functions can be identified exactly, without iterative interrogation. This is another example of quantum search. The resulting positive (or negative) functions also serve to uniquely reorganize a superposition of states to give a basis state for testing purposes.

arXiv:quant-ph/0308157•Aug 28, 2003•0 citations

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

A Generalization of the Deutsch-Jozsa Algorithm to Multi-Valued Quantum Logic

Yale Fan

We generalize the binary Deutsch-Jozsa algorithm to n- valued logic using the quantum Fourier transform. Our algorithm is not only able to distinguish between constant and balanced Boolean functions in a single query, but can also find closed expressions for classes of affine functions in quantum oracles, accurate to a constant term.

arXiv:0809.0932•IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•28 citations

Symmetric functions of qubits in an unknown basis

Ashley Montanaro

Consider an $n$-qubit computational basis state corresponding to a bit-string $x$, which has had an unknown local unitary applied to each qubit, and whose qubits have been reordered by an unknown permutation. We show that, given such a state with Hamming weight $|x|\ensuremath{\le}\ensuremath{\lfloor}n/2\ensuremath{\rfloor}$, it is possible to reconstruct $|x|$ with success-probability $1\ensuremath{-}|x|/(n\ensuremath{-}|x|+1)$, and thus to compute any symmetric function of $x$. We give explicit algorithms for computing whether or not $|x|\ensuremath{\ge}t$ for some $t$, and for computing the parity of $x$, and show that these are essentially optimal. These results can be seen as generalizations of the swap test for comparing quantum states.

arXiv:0903.5466•Physical Review A•Jun 17, 2009•4 citations

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998•Aug 27, 2020•3 citations

Generalized Deutsch-Jozsa problem and the optimal quantum algorithm

Daowen Qiu, Shenggen Zheng

The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as ${\text{DJ}}_{n}^{0}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0$ for $|x|=0,n$, and it is undefined for the rest of the cases, where $n$ is even, and $|x|$ is the Hamming weight of $x$. The optimal quantum algorithm needs only one query to compute ${\text{DJ}}_{n}^{0}$ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as ${\text{DJ}}_{n}^{k}(x)=1$ for $|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0$ for $|x|$ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the generalized Deutsch-Jozsa problem ${\text{DJ}}_{n}^{k}$. It is clear that the case of $k=0$ is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.

Physical Review A•Jun 20, 2018•33 citations
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.
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.
Consider an nnn-qubit computational basis state corresponding to a bit-string xxx, which has had an unknown local unitary applied to each qubit, and whose qubits have been reordered by an unknown permutation. We show that, given such a state with Hamming weight $|x|\ensuremath{\le}\ensuremath{\lfloor}n/2\ensuremath{\rfloor}$, it is possible to reconstruct ∣x∣|x|∣x∣ with success-probability $1\ensuremath{-}|x|/(n\ensuremath{-}|x|+1)$, and thus to compute any symmetric function of xxx. We give explicit algorithms for computing whether or not $|x|\ensuremath{\ge}t$ for some ttt, and for computing the parity of xxx, and show that these are essentially optimal. These results can be seen as generalizations of the swap test for comparing quantum states.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as DJn0(x)=1{\text{DJ}}_{n}^{0}(x)=1DJn0​(x)=1 for ∣x∣=n/2,DJn0(x)=0|x|=n/2, {\text{DJ}}_{n}^{0}(x)=0∣x∣=n/2,DJn0​(x)=0 for ∣x∣=0,n|x|=0,n∣x∣=0,n, and it is undefined for the rest of the cases, where nnn is even, and ∣x∣|x|∣x∣ is the Hamming weight of xxx. The optimal quantum algorithm needs only one query to compute DJn0{\text{DJ}}_{n}^{0}DJn0​ but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJnk(x)=1{\text{DJ}}_{n}^{k}(x)=1DJnk​(x)=1 for ∣x∣=n/2,DJnk(x)=0|x|=n/2, {\text{DJ}}_{n}^{k}(x)=0∣x∣=n/2,DJnk​(x)=0 for ∣x∣|x|∣x∣ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity k+1k+1k+1 for computing the generalized Deutsch-Jozsa problem DJnk{\text{DJ}}_{n}^{k}DJnk​. It is clear that the case of k=0k=0k=0 is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.