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:1803.04114 · New Journal of Physics

Learning the quantum algorithm for state overlap

Lukasz Cincio, Yiğit Subaşı, Andrew T Sornborger, Patrick J Coles

Published Oct 18, 2018• 282 citations
arXivHTMLPDF

Abstract

Short-depth algorithms are crucial for reducing computational error on near-term quantum computers, for which decoherence and gate infidelity remain important issues. Here we present a machine-learning approach for discovering such algorithms. We apply our method to a ubiquitous primitive: computing the overlap between two quantum states ρ and σ . The standard algorithm for this task, known as the Swap Test, is used in many applications such as quantum support vector machines, and, when specialized to ρ = σ , quantifies the Renyi entanglement. Here, we find algorithms that have shorter depths than the Swap Test, including one that has a constant depth (independent of problem size). Furthermore, we apply our approach to the hardware-specific connectivity and gate sets used by Rigetti's and IBM's quantum computers and demonstrate that the shorter algorithms that we derive significantly reduce the error—compared to the Swap Test—on these computers.

DOI
10.1088/1367-2630/aae94a

Related papers

A non-algorithmic approach to “programming” quantum computers via machine learning

Nathan L. Thompson, James E. Steck, Elizabeth Behrman

Major obstacles remain to the implementation of macroscopic quantum computing: hardware problems of noise, decoherence, and scaling; software problems of error correction; and, most important, algorithm construction. Finding truly quantum algorithms is quite difficult, and many of these genuine quantum algorithms, like Shor's prime factoring or phase estimation, require extremely long circuit depth for any practical application, which necessitates error correction. In contrast, we show that machine learning can be used as a systematic method to construct algorithms, that is, to non-algorithmically “program” quantum computers. Quantum machine learning enables us to perform computations without breaking down an algorithm into its gate “building blocks”, eliminating that difficult step and potentially increasing efficiency by simplifying and reducing unnecessary complexity. In addition, our non-algorithmic machine learning approach is robust to both noise and to decoherence, which is ideal for running on inherently noisy NISQ devices which are limited in the number of qubits available for error correction. We demonstrate this using a fundamentally nonclassical calculation: experimentally estimating the entanglement of an unknown quantum state. Results from this have been successfully ported to the IBM hardware and trained using a hybrid reinforcement learning method.

arXiv:2007.08327•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•6 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•3 citations

Multi-state Swap Test Algorithm

Wen Liu, Han-Wen Yin, Zhi-Rao Wang +1 more

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 we designed a recursive quantum circuit to measure overlaps of multiple quantum states $|ϕ_1...ϕ_n\rangle$ concurrently with $O(n\log n)$ controlled-swap (CSWAP) gates and $O(\log n)$ ancillary qubits. This circuit enables us to get all pairwise overlaps among input quantum states $|\langleϕ_i|ϕ_j\rangle|^2$. Compared with existing schemes for measuring the overlap of multiple quantum states, our scheme provides higher precision and less consumption of ancillary qubits. In addition, we performed simulation experiments on IBM quantum cloud platform to verify the superiority of the scheme.

arXiv:2205.07171•May 15, 2022•1 citation

Variational quantum state diagonalization

Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy +2 more

Abstract Variational hybrid quantum-classical algorithms are promising candidates for near-term implementation on quantum computers. In these algorithms, a quantum computer evaluates the cost of a gate sequence (with speedup over classical cost evaluation), and a classical computer uses this information to adjust the parameters of the gate sequence. Here we present such an algorithm for quantum state diagonalization. State diagonalization has applications in condensed matter physics (e.g., entanglement spectroscopy) as well as in machine learning (e.g., principal component analysis). For a quantum state ρ and gate sequence U, our cost function quantifies how far $$U\rho U^\dagger$$ U ρ U † is from being diagonal. We introduce short-depth quantum circuits to quantify our cost. Minimizing this cost returns a gate sequence that approximately diagonalizes ρ. One can then read out approximations of the largest eigenvalues, and the associated eigenvectors, of ρ. As a proof-of-principle, we implement our algorithm on Rigetti’s quantum computer to diagonalize one-qubit states and on a simulator to find the entanglement spectrum of the Heisenberg model ground state.

arXiv:1810.10506•npj Quantum Information•Jun 26, 2019•195 citations

Entanglement spectroscopy with a depth-two quantum circuit

Yiğit Subaşı, Łukasz Cincio, Patrick J. Coles

Abstract Noisy intermediate-scale quantum (NISQ) computers have gate errors and decoherence, limiting the depth of circuits that can be implemented on them. A strategy for NISQ algorithms is to reduce the circuit depth at the expense of increasing the qubit count. Here, we exploit this trade-off for an application called entanglement spectroscopy, where one computes the entanglement of a state on systems by evaluating the Rényi entropy of the reduced state . For a -qubit state , the Rényi entropy of order is computed via , with the complexity growing exponentially in for classical computers. Johri et al (2017 Phys. Rev . B 96 195136) introduced a quantum algorithm that requires copies of and whose depth scales linearly in . Here, we present a quantum algorithm requiring twice the qubit resources ( copies of ) but with a depth that is independent of both and . Surprisingly this depth is only two gates. Our numerical simulations show that this short depth leads to an increased robustness to noise.

arXiv:1806.08863•Journal of Physics A Mathematical and Theoretical•Nov 30, 2018•52 citations

Quantum-assisted quantum compiling

Sumeet Khatri, Ryan LaRose, Alexander Poremba +3 more

Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary U and a trainable unitary V as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap T r ( V † U ) but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.

arXiv:1807.00800•Quantum•May 13, 2019•380 citations
Short-depth algorithms are crucial for reducing computational error on near-term quantum computers, for which decoherence and gate infidelity remain important issues. Here we present a machine-learning approach for discovering such algorithms. We apply our method to a ubiquitous primitive: computing the overlap between two quantum states ρ and σ . The standard algorithm for this task, known as the Swap Test, is used in many applications such as quantum support vector machines, and, when specialized to ρ = σ , quantifies the Renyi entanglement. Here, we find algorithms that have shorter depths than the Swap Test, including one that has a constant depth (independent of problem size). Furthermore, we apply our approach to the hardware-specific connectivity and gate sets used by Rigetti's and IBM's quantum computers and demonstrate that the shorter algorithms that we derive significantly reduce the error—compared to the Swap Test—on these computers.
Major obstacles remain to the implementation of macroscopic quantum computing: hardware problems of noise, decoherence, and scaling; software problems of error correction; and, most important, algorithm construction. Finding truly quantum algorithms is quite difficult, and many of these genuine quantum algorithms, like Shor's prime factoring or phase estimation, require extremely long circuit depth for any practical application, which necessitates error correction. In contrast, we show that machine learning can be used as a systematic method to construct algorithms, that is, to non-algorithmically “program” quantum computers. Quantum machine learning enables us to perform computations without breaking down an algorithm into its gate “building blocks”, eliminating that difficult step and potentially increasing efficiency by simplifying and reducing unnecessary complexity. In addition, our non-algorithmic machine learning approach is robust to both noise and to decoherence, which is ideal for running on inherently noisy NISQ devices which are limited in the number of qubits available for error correction. We demonstrate this using a fundamentally nonclassical calculation: experimentally estimating the entanglement of an unknown quantum state. Results from this have been successfully ported to the IBM hardware and trained using a hybrid reinforcement learning method.
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.
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 we designed a recursive quantum circuit to measure overlaps of multiple quantum states ∣ϕ1...ϕn⟩|ϕ_1...ϕ_n\rangle∣ϕ1​...ϕn​⟩ concurrently with O(nlog⁡n)O(n\log n)O(nlogn) controlled-swap (CSWAP) gates and O(log⁡n)O(\log n)O(logn) ancillary qubits. This circuit enables us to get all pairwise overlaps among input quantum states ∣⟨ϕi∣ϕj⟩∣2|\langleϕ_i|ϕ_j\rangle|^2∣⟨ϕi​∣ϕj​⟩∣2. Compared with existing schemes for measuring the overlap of multiple quantum states, our scheme provides higher precision and less consumption of ancillary qubits. In addition, we performed simulation experiments on IBM quantum cloud platform to verify the superiority of the scheme.
Abstract Variational hybrid quantum-classical algorithms are promising candidates for near-term implementation on quantum computers. In these algorithms, a quantum computer evaluates the cost of a gate sequence (with speedup over classical cost evaluation), and a classical computer uses this information to adjust the parameters of the gate sequence. Here we present such an algorithm for quantum state diagonalization. State diagonalization has applications in condensed matter physics (e.g., entanglement spectroscopy) as well as in machine learning (e.g., principal component analysis). For a quantum state ρ and gate sequence U, our cost function quantifies how far UρU†U\rho U^\daggerUρU† U ρ U † is from being diagonal. We introduce short-depth quantum circuits to quantify our cost. Minimizing this cost returns a gate sequence that approximately diagonalizes ρ. One can then read out approximations of the largest eigenvalues, and the associated eigenvectors, of ρ. As a proof-of-principle, we implement our algorithm on Rigetti’s quantum computer to diagonalize one-qubit states and on a simulator to find the entanglement spectrum of the Heisenberg model ground state.
Abstract Noisy intermediate-scale quantum (NISQ) computers have gate errors and decoherence, limiting the depth of circuits that can be implemented on them. A strategy for NISQ algorithms is to reduce the circuit depth at the expense of increasing the qubit count. Here, we exploit this trade-off for an application called entanglement spectroscopy, where one computes the entanglement of a state on systems by evaluating the Rényi entropy of the reduced state . For a -qubit state , the Rényi entropy of order is computed via , with the complexity growing exponentially in for classical computers. Johri et al (2017 Phys. Rev . B 96 195136) introduced a quantum algorithm that requires copies of and whose depth scales linearly in . Here, we present a quantum algorithm requiring twice the qubit resources ( copies of ) but with a depth that is independent of both and . Surprisingly this depth is only two gates. Our numerical simulations show that this short depth leads to an increased robustness to noise.
Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary U and a trainable unitary V as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap T r ( V † U ) but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.