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

Springer eBooks

A Survey: SWAP Test and Its Applications to Quantum Complexity Theory

Harumichi Nishimura

Published Jan 1, 2025• 8 citations
Publisher

Abstract

Abstract The SWAP test is a fundamental tool commonly used in the theory of quantum information and computation while its understanding and applications have been investigated in the literature. This survey focuses on the SWAP test in the studies of quantum complexity theory. We review the basics of the SWAP test, some tests related to it, and their properties, and report their applications in quantum complexity theory.

DOI
10.1007/978-981-96-0668-9_16

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

On quantum methods for machine learning problems part I: Quantum tools

Farid Mansurovich Ablayev, Marat Ablayev, Joshua Zhexue Huang +3 more

This is a review of quantum methods for machine learning problems that consists of two parts. The first part, “quantum tools”, presents the fundamentals of qubits, quantum registers, and quantum states, introduces important quantum tools based on known quantum search algorithms and SWAP-test, and discusses the basic quantum procedures used for quantum search methods. The second part, “quantum classification algorithms”, introduces several classification problems that can be accelerated by using quantum subroutines and discusses the quantum methods used for classification.

Big Data Mining and Analytics•Dec 19, 2019•67 citations

Counting complexity and quantum computation

Stephen Fenner

Abstract We survey several applications to quantum computing of computational complexity theory, especially the complexity of problems related to counting. We show how the connection of quantum computation to counting is very close. We define counting complexity classes, relativization of both classical computation and quantum circuits, and present a number of results from disparate sources, recast into a single consistent formalism. We assume prior knowledge of the mathematical formalism of quantum mechanics, but we present the concepts of computational complexity in an introductory manner.

Chapman & Hall/CRC eBooks•Feb 14, 2002•2 citations

Quantum memory devices -fabrication, characterizations, and material platforms: a review

Peddarapu Lakshmi Narayani, Laxmi Narayan Tripathi

Abstract Quantum memory devices are essential components of integrated quantum-photonic circuits with applications in quantum computing and quantum information processing. The comprehension and quantification of critical properties such as fidelity, coherence time, storage time, and efficiency of quantum memory are insufficient in the extant literature. In this review, we examine the development and characteristics of various types of quantum memories. Although diverse approaches to storing quantum information are described in detail, we emphasize solid-state quantum memory. Furthermore, we discuss the fabrication and characterization of defects of quantum materials, including two-dimensional materials, for quantum memory applications. We survey theoretical tools such as density functional theory for studying defects to evaluate quantum properties.

Physica Scripta•Jan 16, 2026•0 citations

The controlled SWAP test for determining quantum entanglement

Steph Foulds, Viv M. Kendon, Timothy P. Spiller

Abstract Quantum entanglement is essential to the development of quantum computation, communications, and technology. The controlled SWAP test, widely used for state comparison, can be adapted to an efficient and useful test for entanglement of a pure state. Here we show that the test can evidence the presence of entanglement (and further, genuine n-qubit entanglement), can distinguish entanglement classes, and that the concurrence of a two-qubit state is related to the test’s output probabilities. We also propose a multipartite measure of entanglement that acts similarly for n-qubit states. The average number of copies of the test state required to detect entanglement decreases for larger systems, to four on average for many (n ≳ 8) qubits for maximally entangled states. For non-maximally entangled states, the number of copies required to detect entanglement increases with decreasing entanglement. Furthermore, the results are robust to second order when typical small errors are introduced to the state under investigation.

arXiv:2009.07613•Quantum Science and Technology•Feb 9, 2021•57 citations

A Survey of Bargmann Invariants: Geometric Foundations and Applications

Lin Zhang, Bing Xie

Bargmann invariants, a class of unitary-invariant quantities arising from the overlaps of quantum state vectors, provide a profound and unifying framework for understanding the relative geometry of the projective Hilbert space. This survey offers a comprehensive overview of their theoretical characterization and practical applications, with particular emphasis on recent progress in determining the full structure of their admissible set. The core of this review demonstrates how these invariants serve as a powerful tool for characterizing the intrinsic geometry of the space of quantum states, leading to applications in determining local unitary equivalence and constructing a complete set of polynomial invariants for mixed states. On the operational side, we review the cycle-test quantum circuit for the direct estimation of Bargmann invariants without full state tomography, and demonstrate their utility in witnessing quantum imaginary, discriminating local unitary equivalence, and detecting entanglement via partial-transpose moments---with explicit complete invariant sets provided for two-qubit systems. By connecting fundamental geometric classification with experimentally feasible estimation protocols,this survey establishes Bargmann invariants as indispensable probes of the relational, noncommutative, and geometric structure of quantum states, and identifies key open problems for multipartite high-dimensional systems and for quantum resource theories.

quant-pharXiv:2601.01858•Jan 6, 2026•11 citations
Abstract The SWAP test is a fundamental tool commonly used in the theory of quantum information and computation while its understanding and applications have been investigated in the literature. This survey focuses on the SWAP test in the studies of quantum complexity theory. We review the basics of the SWAP test, some tests related to it, and their properties, and report their applications in quantum complexity theory.
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.
This is a review of quantum methods for machine learning problems that consists of two parts. The first part, “quantum tools”, presents the fundamentals of qubits, quantum registers, and quantum states, introduces important quantum tools based on known quantum search algorithms and SWAP-test, and discusses the basic quantum procedures used for quantum search methods. The second part, “quantum classification algorithms”, introduces several classification problems that can be accelerated by using quantum subroutines and discusses the quantum methods used for classification.
Abstract We survey several applications to quantum computing of computational complexity theory, especially the complexity of problems related to counting. We show how the connection of quantum computation to counting is very close. We define counting complexity classes, relativization of both classical computation and quantum circuits, and present a number of results from disparate sources, recast into a single consistent formalism. We assume prior knowledge of the mathematical formalism of quantum mechanics, but we present the concepts of computational complexity in an introductory manner.
Abstract Quantum memory devices are essential components of integrated quantum-photonic circuits with applications in quantum computing and quantum information processing. The comprehension and quantification of critical properties such as fidelity, coherence time, storage time, and efficiency of quantum memory are insufficient in the extant literature. In this review, we examine the development and characteristics of various types of quantum memories. Although diverse approaches to storing quantum information are described in detail, we emphasize solid-state quantum memory. Furthermore, we discuss the fabrication and characterization of defects of quantum materials, including two-dimensional materials, for quantum memory applications. We survey theoretical tools such as density functional theory for studying defects to evaluate quantum properties.
Abstract Quantum entanglement is essential to the development of quantum computation, communications, and technology. The controlled SWAP test, widely used for state comparison, can be adapted to an efficient and useful test for entanglement of a pure state. Here we show that the test can evidence the presence of entanglement (and further, genuine n-qubit entanglement), can distinguish entanglement classes, and that the concurrence of a two-qubit state is related to the test’s output probabilities. We also propose a multipartite measure of entanglement that acts similarly for n-qubit states. The average number of copies of the test state required to detect entanglement decreases for larger systems, to four on average for many (n ≳ 8) qubits for maximally entangled states. For non-maximally entangled states, the number of copies required to detect entanglement increases with decreasing entanglement. Furthermore, the results are robust to second order when typical small errors are introduced to the state under investigation.
Bargmann invariants, a class of unitary-invariant quantities arising from the overlaps of quantum state vectors, provide a profound and unifying framework for understanding the relative geometry of the projective Hilbert space. This survey offers a comprehensive overview of their theoretical characterization and practical applications, with particular emphasis on recent progress in determining the full structure of their admissible set. The core of this review demonstrates how these invariants serve as a powerful tool for characterizing the intrinsic geometry of the space of quantum states, leading to applications in determining local unitary equivalence and constructing a complete set of polynomial invariants for mixed states. On the operational side, we review the cycle-test quantum circuit for the direct estimation of Bargmann invariants without full state tomography, and demonstrate their utility in witnessing quantum imaginary, discriminating local unitary equivalence, and detecting entanglement via partial-transpose moments---with explicit complete invariant sets provided for two-qubit systems. By connecting fundamental geometric classification with experimentally feasible estimation protocols,this survey establishes Bargmann invariants as indispensable probes of the relational, noncommutative, and geometric structure of quantum states, and identifies key open problems for multipartite high-dimensional systems and for quantum resource theories.