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:0809.2037 · Journal of Physics A Mathematical and Theoretical

The efficiency of quantum identity testing of multiple states

Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami

Published Sep 8, 2008• 25 citations
arXivHTMLPDF

Abstract

We examine two quantum operations, the permutation test and the circle test, which test the identity of n quantum states. These operations naturally extend the well-studied swap test on two quantum states. We first show the optimality of the permutation test for any input size n as well as the optimality of the circle test for three input states. In particular, when n = 3, we present a semi-classical protocol, incorporated with the swap test, which approximates the circle test efficiently. Furthermore, we show that, with the help of classical preprocessing, a single use of the circle test can approximate the permutation test efficiently for an arbitrary input size n .

DOI
10.1088/1751-8113/41/39/395309

Related papers

Quantum Time Lower Bounds by Permutation Invariance

Qisheng Wang

Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(ρ^2)$ and the inner product $\operatorname{tr}(ρσ)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(ρ^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.

quant-pharXiv:2606.05099•Jun 4, 2026•0 citations

Permutation tests for quantum state identity

Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel +1 more

The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether $n$ unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of the quantum state identity problem. Using tools from semidefinite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general $G$-test which uses an arbitrary subgroup $G$ of $\text{S}_n$, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and $n-1$ Swap tests.

arXiv:2405.09626•May 15, 2024•12 citations

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.

quant-pharXiv:2610.04597•Oct 6, 2026•0 citations

An arbitrated quantum signature scheme for classical information using entanglement swapping

Jason Lin, Mei-Yen Yen, Chia‐Wei Tsai +1 more

Quantum signature protocols often rely on quantum states to carry signature information directly. However, they need SWAP tests, which require numerous copies to ensure accuracy and security, resulting in high implementation costs. This study proposes an arbitrated quantum signature protocol that incorporates classical information with entanglement swapping. Quantum states are converted into classical information immediately after measurement. The protocol does not rely on SWAP tests, avoids long-term storage of quantum signatures, and employs exclusive-OR operations and hash functions to process signature data. By leveraging a third-party arbitrator, it enables reliable identity verification of the signer and verifier, thereby guaranteeing unforgeability and nonrepudiation.

EPJ Quantum Technology•Mar 19, 2026•0 citations

Quantum Algorithms to Matrix Multiplication

Changpeng Shao

In this paper, we study quantum algorithms of matrix multiplication from the viewpoint of inputting quantum/classical data to outputting quantum/classical data. The main target is trying to overcome the input and output problem, which are not easy to solve and many quantum algorithms will encounter, to study matrix operations in quantum computer with high efficiency. And solving matrix multiplication will be the first step. We propose three quantum algorithms to matrix multiplication based on swap test, SVE and HHL. From the point of making fewer assumptions, swap test method works the best than the other two. We also show that the quantum algorithm of matrix multiplication with classical input and output data by swap test achieves the best complexity $\widetilde{O}(n^2/ε)$ with no assumptions. This is proved by giving an efficient quantum algorithm in polynomial time to solve the input problem, that is to prepare the quantum states of the classical data efficiently. Other contributions of this paper include: (1). Extending swap test to a more general form that is suitable to deal with quantum data in parallel, which will have further applications in other matrix operations. (2). Generalizing SVE technique such that it applies to any matrix (not just Hermitian) directly only with quantum data. (3). Proposing two new efficient quantum algorithms to prepare quantum states of classical data, which solves the input problem efficiently than other quantum algorithms.

arXiv:1803.01601•Mar 5, 2018•34 citations

Quantum multi-state Swap Test: an algorithm for estimating overlaps of arbitrary number quantum states

Wen Liu, Yang-Zhi Li, Han-Wen Yin +2 more

Abstract Estimating the overlap between two states is an important task with several applications in quantum information. However, the typical swap test circuit can only measure a sole pair of quantum states at a time. In this study, a recursive quantum circuit is designed to measure overlaps of n quantum states $\left | {\phi _{1} } \right \rangle ,\left | {\phi _{2} } \right \rangle ,\ldots\left | {\phi _{n} }\right \rangle $ | ϕ 1 〉 , | ϕ 2 〉 , … | ϕ n 〉 concurrently with $O(k2^{k})$ O ( k 2 k ) controlled-swap(CSWAP) gates and $O(k)$ O ( k ) ancillary qubits, where $k=\left \lceil {\log n} \right \rceil $ k = ⌈ log n ⌉ . All pairwise overlaps among input quantum states $|\langle \phi _{i}|\phi _{j}\rangle |^{2}$ | 〈 ϕ i | ϕ j 〉 | 2 can be obtained in this circuit. Compared with existing scheme for measuring the overlap of multiple quantum states, the circuit provides higher precision and less consumption of ancillary qubits. In addition, some simulation experiments are performed on IBM quantum cloud platform to verify the superiority of this algorithm.

EPJ Quantum Technology•Jul 25, 2024•4 citations
We examine two quantum operations, the permutation test and the circle test, which test the identity of n quantum states. These operations naturally extend the well-studied swap test on two quantum states. We first show the optimality of the permutation test for any input size n as well as the optimality of the circle test for three input states. In particular, when n = 3, we present a semi-classical protocol, incorporated with the swap test, which approximates the circle test efficiently. Furthermore, we show that, with the help of classical preprocessing, a single use of the circle test can approximate the permutation test efficiently for an arbitrary input size n .
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr⁡(ρ2)\operatorname{tr}(ρ^2)tr(ρ2) and the inner product tr⁡(ρσ)\operatorname{tr}(ρσ)tr(ρσ). 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr⁡(ρk)\operatorname{tr}(ρ^k)tr(ρk). 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
The quantum analogue of the equality function, known as the quantum state identity problem, is the task of deciding whether nnn unknown quantum states are equal or unequal, given the promise that all states are either pairwise orthogonal or identical. Under the one-sided error requirement, it is known that the permutation test is optimal for this task, and for two input states this coincides with the well-known Swap test. Until now, the optimal measurement in the general two-sided error regime was unknown. Under more specific promises, the problem can be solved approximately or even optimally with simpler tests, such as the circle test. This work attempts to capture the underlying structure of the quantum state identity problem. Using tools from semidefinite programming and representation theory, we (i) give an optimal test for any input distribution without the one-sided error requirement by writing the problem as an SDP, giving the exact solutions to the primal and dual programs and showing that the two values coincide; (ii) propose a general GGG-test which uses an arbitrary subgroup GGG of Sn\text{S}_nSn​, giving an analytic expression of the performance of the specific test, and (iii) give an approximation of the permutation test using only a classical permutation and n−1n-1n−1 Swap tests.
We study the following quantum state identity problem: given access to copies of nnn unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε1-\varepsilon1−ε or some pair has fidelity at most ε\varepsilonε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4)\varepsilon\in(0,1/4)ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log⁡(n/δ)log⁡(2/δ))O(\log(n/δ)\log(2/δ))O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ1-δ1−δ. The second uses the Schur transform to reduce the sample complexity to O(log⁡(n/δ))O(\log(n/δ))O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log⁡(n/δ))Ω(\log(n/δ))Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−cδ\le 1/2-cδ≤1/2−c, for any constant c>0c>0c>0, establishing that the second algorithm achieves the optimal dependence on both nnn and δδδ for fixed ε\varepsilonε.
Quantum signature protocols often rely on quantum states to carry signature information directly. However, they need SWAP tests, which require numerous copies to ensure accuracy and security, resulting in high implementation costs. This study proposes an arbitrated quantum signature protocol that incorporates classical information with entanglement swapping. Quantum states are converted into classical information immediately after measurement. The protocol does not rely on SWAP tests, avoids long-term storage of quantum signatures, and employs exclusive-OR operations and hash functions to process signature data. By leveraging a third-party arbitrator, it enables reliable identity verification of the signer and verifier, thereby guaranteeing unforgeability and nonrepudiation.
In this paper, we study quantum algorithms of matrix multiplication from the viewpoint of inputting quantum/classical data to outputting quantum/classical data. The main target is trying to overcome the input and output problem, which are not easy to solve and many quantum algorithms will encounter, to study matrix operations in quantum computer with high efficiency. And solving matrix multiplication will be the first step. We propose three quantum algorithms to matrix multiplication based on swap test, SVE and HHL. From the point of making fewer assumptions, swap test method works the best than the other two. We also show that the quantum algorithm of matrix multiplication with classical input and output data by swap test achieves the best complexity O~(n2/ε)\widetilde{O}(n^2/ε)O(n2/ε) with no assumptions. This is proved by giving an efficient quantum algorithm in polynomial time to solve the input problem, that is to prepare the quantum states of the classical data efficiently. Other contributions of this paper include: (1). Extending swap test to a more general form that is suitable to deal with quantum data in parallel, which will have further applications in other matrix operations. (2). Generalizing SVE technique such that it applies to any matrix (not just Hermitian) directly only with quantum data. (3). Proposing two new efficient quantum algorithms to prepare quantum states of classical data, which solves the input problem efficiently than other quantum algorithms.
Abstract Estimating the overlap between two states is an important task with several applications in quantum information. However, the typical swap test circuit can only measure a sole pair of quantum states at a time. In this study, a recursive quantum circuit is designed to measure overlaps of n quantum states $\left | {\phi _{1} } \right \rangle ,\left | {\phi _{2} } \right \rangle ,\ldots\left | {\phi _{n} }\right \rangle $ | ϕ 1 〉 , | ϕ 2 〉 , … | ϕ n 〉 concurrently with O(k2k)O(k2^{k})O(k2k) O ( k 2 k ) controlled-swap(CSWAP) gates and O(k)O(k)O(k) O ( k ) ancillary qubits, where $k=\left \lceil {\log n} \right \rceil $ k = ⌈ log n ⌉ . All pairwise overlaps among input quantum states ∣⟨ϕi∣ϕj⟩∣2|\langle \phi _{i}|\phi _{j}\rangle |^{2}∣⟨ϕi​∣ϕj​⟩∣2 | 〈 ϕ i | ϕ j 〉 | 2 can be obtained in this circuit. Compared with existing scheme for measuring the overlap of multiple quantum states, the circuit provides higher precision and less consumption of ancillary qubits. In addition, some simulation experiments are performed on IBM quantum cloud platform to verify the superiority of this algorithm.