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:quant-ph/0510159 · Physical Review A

Quantitative measure of interference

Daniel Braun, Bertrand Georgeot

Published Feb 7, 2006• 34 citations
arXivHTMLPDF

Abstract

We introduce an interference measure which allows to quantify the amount of interference present in any physical process that maps an initial density matrix to a final density matrix. In particular, the interference measure enables one to monitor the amount of interference generated in each step of a quantum algorithm. We show that a Hadamard gate acting on a single qubit is a basic building block for interference generation and realizes one bit of interference, an ``ibit.'' We use the interference measure to quantify interference for various examples, including Grover's search algorithm and Shor's factorization algorithm. We distinguish between ``potentially available'' and ``actually used'' interference, and show that for both algorithms the potentially available interference is exponentially large. However, the amount of interference actually used in Grover's algorithm is only about $3\phantom{\rule{0.3em}{0ex}}\mathrm{ibits}$ and asymptotically independent of the number of qubits, while Shor's algorithm indeed uses an exponential amount of interference.

DOI
10.1103/physreva.73.022314

Related papers

Interference versus success probability in quantum algorithms with imperfections

Daniel Braun, Bertrand Georgeot

We study the importance of interference for the performance of Shor's factoring algorithm and Grover's search algorithm using a recently proposed interference measure. To this aim we introduce systematic unitary errors, random unitary errors, and decoherence processes in these algorithms. We show that unitary errors which destroy the interference destroy the efficiency of the algorithm, too. However, unitary errors may also create useless additional interference. In such a case the total amount of interference can increase, while the efficiency of the quantum computation decreases. For decoherence due to phase flip errors, interference is destroyed for small error probabilities, and converted into destructive interference for error probabilities approaching 1, leading to success probabilities which can even drop below the classical value. Our results show that in general, interference is necessary in order for a quantum algorithm to outperform classical computation, but large amounts of interference are not sufficient and can even lead to destructive interference with worse than classical success rates.

arXiv:0711.1513•Physical Review A•Feb 14, 2008•7 citations

Entanglement Monotones and Measures: An Overview

Volkan Erol

Quantum information theory and quantum computing are theoritical basis of quantum computers. Thanks to entanglement, quantum mechanical systems are provisioned to realize many information processing problems faster than classical counterparts. For example, Shor’s factorization algorithm, Grover’s search algorithm, quantum Fourrier transformation, etc. [1]. Entanglement, is the theoretical basis providing the expected speedups. It can be view in bipartite or multipartite forms. In order to quantify entanglement, some measures are defined. On the other hand, a general and accepted criterion, which can measure the amount of entanglement of multilateral systems, has not yet been found. However, since it must be used in many information processing tasks, the production and processing of multilateral quantum entangled systems is at the top of the hot topics of recent years [5-11]. Much of the work in the basic quantum technologies, such as quantum cryptography, communications, and computers, requires multi-partite entangled systems such as GHZ, W [22,30]. It can be suggested that the quantum entanglement criteria reflects the different properties of the systems. Many recent research has been done in entanglement and its related disciplines like entanglement measures and majorization, etc. [62-71]. In this work, we make an overview of recent research on the topic entanglement monotones/measures with an analitical approach.

arXiv:1704.05058•Apr 17, 2017•5 citations

Near-perfect Reachability of Variational Quantum Search with Depth-1 Ansatz

Junpeng Zhan

Grover's search algorithm is renowned for its dramatic speedup in solving many important scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. However, its advantage for larger numbers of qubits has not yet been proven. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate together with either a single layer of Ry gates or two layers of circuits consisting of Hadamard and NOT gates, which is valid for any number of qubits greater than five. We prove that the VQS, with a single layer of Ry gates as its Ansatz, has near-perfect reachability in finding the good element of an arbitrarily large unstructured data set, and its reachability exponentially improves with the number of qubits, where the reachability is defined to quantify the ability of a given Ansatz to generate an optimal quantum state. Numerical studies further validate the excellent reachability of the VQS. Proving the near-perfect reachability of the VQS, with a depth-1 Ansatz, for any number of qubits completes an essential step in proving its exponential advantage over Grover's algorithm for any number of qubits, and the latter proving is significant as it means that the VQS can efficiently solve NP-complete problems.

arXiv:2301.13224•Jan 30, 2023•1 citation

Measuring quantum coherence in multislit interference

Tania Paul, Tabish Qureshi

A quantitative measure of quantum coherence was recently introduced in the context of quantum information theory. This measure has also been propounded as a good quantifier of the wave nature of quantum objects. However, actually measuring coherence in an experiment is still considered a challenge. A procedure for measuring coherence in a multislit interference is proposed here. It can be used for experimentally testing duality relations for interference experiments involving more than two slits.

arXiv:1701.09091•Physical Review A•Apr 10, 2017•41 citations

Measurement-Based Interference in Quantum Computation

You-Yang Xu

The interference has been measured by the visibility in two-level systems, which, however, does not work for multi-level systems. We generalize a measure of the interference based on decoherence process, consistent with the visibility in qubit systems. By taking cluster states as examples, we show in the one-way quantum computation that the gate fidelity is proportional to the interference of the measured qubit and is inversely proportional to the interference of all register qubits. We also find that the interference increases with the number of the computing steps. So we conjecture that the interference may be the source of the speedup of the one-way quantum computation.

Communications in Theoretical Physics•Sep 1, 2013•4 citations

Quantum Simulation of Tunneling in Small Systems

Andrew T. Sornborger

A number of quantum algorithms have been performed on small quantum computers; these include Shor's prime factorization algorithm, error correction, Grover's search algorithm and a number of analog and digital quantum simulations. Because of the number of gates and qubits necessary, however, digital quantum particle simulations remain untested. A contributing factor to the system size required is the number of ancillary qubits needed to implement matrix exponentials of the potential operator. Here, we show that a set of tunneling problems may be investigated with no ancillary qubits and a cost of one single-qubit operator per time step for the potential evolution, eliminating at least half of the quantum gates required for the algorithm and more than that in the general case. Such simulations are within reach of current quantum computer architectures.

arXiv:1202.1536•Scientific Reports•Aug 22, 2012•25 citations
We introduce an interference measure which allows to quantify the amount of interference present in any physical process that maps an initial density matrix to a final density matrix. In particular, the interference measure enables one to monitor the amount of interference generated in each step of a quantum algorithm. We show that a Hadamard gate acting on a single qubit is a basic building block for interference generation and realizes one bit of interference, an ibit.'' We use the interference measure to quantify interference for various examples, including Grover's search algorithm and Shor's factorization algorithm. We distinguish between potentially available'' and ``actually used'' interference, and show that for both algorithms the potentially available interference is exponentially large. However, the amount of interference actually used in Grover's algorithm is only about 3ibits3\phantom{\rule{0.3em}{0ex}}\mathrm{ibits}3ibits and asymptotically independent of the number of qubits, while Shor's algorithm indeed uses an exponential amount of interference.
We study the importance of interference for the performance of Shor's factoring algorithm and Grover's search algorithm using a recently proposed interference measure. To this aim we introduce systematic unitary errors, random unitary errors, and decoherence processes in these algorithms. We show that unitary errors which destroy the interference destroy the efficiency of the algorithm, too. However, unitary errors may also create useless additional interference. In such a case the total amount of interference can increase, while the efficiency of the quantum computation decreases. For decoherence due to phase flip errors, interference is destroyed for small error probabilities, and converted into destructive interference for error probabilities approaching 1, leading to success probabilities which can even drop below the classical value. Our results show that in general, interference is necessary in order for a quantum algorithm to outperform classical computation, but large amounts of interference are not sufficient and can even lead to destructive interference with worse than classical success rates.
Quantum information theory and quantum computing are theoritical basis of quantum computers. Thanks to entanglement, quantum mechanical systems are provisioned to realize many information processing problems faster than classical counterparts. For example, Shor’s factorization algorithm, Grover’s search algorithm, quantum Fourrier transformation, etc. [1]. Entanglement, is the theoretical basis providing the expected speedups. It can be view in bipartite or multipartite forms. In order to quantify entanglement, some measures are defined. On the other hand, a general and accepted criterion, which can measure the amount of entanglement of multilateral systems, has not yet been found. However, since it must be used in many information processing tasks, the production and processing of multilateral quantum entangled systems is at the top of the hot topics of recent years [5-11]. Much of the work in the basic quantum technologies, such as quantum cryptography, communications, and computers, requires multi-partite entangled systems such as GHZ, W [22,30]. It can be suggested that the quantum entanglement criteria reflects the different properties of the systems. Many recent research has been done in entanglement and its related disciplines like entanglement measures and majorization, etc. [62-71]. In this work, we make an overview of recent research on the topic entanglement monotones/measures with an analitical approach.
Grover's search algorithm is renowned for its dramatic speedup in solving many important scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. However, its advantage for larger numbers of qubits has not yet been proven. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate together with either a single layer of Ry gates or two layers of circuits consisting of Hadamard and NOT gates, which is valid for any number of qubits greater than five. We prove that the VQS, with a single layer of Ry gates as its Ansatz, has near-perfect reachability in finding the good element of an arbitrarily large unstructured data set, and its reachability exponentially improves with the number of qubits, where the reachability is defined to quantify the ability of a given Ansatz to generate an optimal quantum state. Numerical studies further validate the excellent reachability of the VQS. Proving the near-perfect reachability of the VQS, with a depth-1 Ansatz, for any number of qubits completes an essential step in proving its exponential advantage over Grover's algorithm for any number of qubits, and the latter proving is significant as it means that the VQS can efficiently solve NP-complete problems.
A quantitative measure of quantum coherence was recently introduced in the context of quantum information theory. This measure has also been propounded as a good quantifier of the wave nature of quantum objects. However, actually measuring coherence in an experiment is still considered a challenge. A procedure for measuring coherence in a multislit interference is proposed here. It can be used for experimentally testing duality relations for interference experiments involving more than two slits.
The interference has been measured by the visibility in two-level systems, which, however, does not work for multi-level systems. We generalize a measure of the interference based on decoherence process, consistent with the visibility in qubit systems. By taking cluster states as examples, we show in the one-way quantum computation that the gate fidelity is proportional to the interference of the measured qubit and is inversely proportional to the interference of all register qubits. We also find that the interference increases with the number of the computing steps. So we conjecture that the interference may be the source of the speedup of the one-way quantum computation.
A number of quantum algorithms have been performed on small quantum computers; these include Shor's prime factorization algorithm, error correction, Grover's search algorithm and a number of analog and digital quantum simulations. Because of the number of gates and qubits necessary, however, digital quantum particle simulations remain untested. A contributing factor to the system size required is the number of ancillary qubits needed to implement matrix exponentials of the potential operator. Here, we show that a set of tunneling problems may be investigated with no ancillary qubits and a cost of one single-qubit operator per time step for the potential evolution, eliminating at least half of the quantum gates required for the algorithm and more than that in the general case. Such simulations are within reach of current quantum computer architectures.