Coherence Fraction in Grover Search Algorithm
arXiv:2511.06835 · doi:10.1103/physreva.110.062429
Abstract
The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.
9 pages, 6 figures. Published in Physical Review A 110, 062429 (2024)
References in corpus (35)
- Quantum entanglement
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Machine Learning
- Quantum Computing
- Quantum algorithm for solving linear systems of equations
- Quantum Simulation
- Quantifying Coherence
- Entanglement detection
- Quantum computational advantage using photons
- Quantum support vector machine for big data classification
- Quantum Coherence as a Resource
- An introduction to quantum machine learning
- Quantum discord and the power of one qubit
- Quantum Computational Supremacy
- A blueprint for demonstrating quantum supremacy with superconducting qubits
- The resource theory of quantum reference frames: manipulations and monotones
- Extending Noether's theorem by quantifying the asymmetry of quantum states
- Quantum coherence and geometric quantum discord
- Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
- Coherence depletion in the Grover quantum search algorithm
- Resource-Efficient Quantum Algorithm for Protein Folding
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
- Towards quantum enhanced adversarial robustness in machine learning
- Experimental progress on quantum coherence: detection, quantification, and manipulation
- On the Role of Coherence in Shor's Algorithm
- Experimental quantification of coherence of a tunable quantum detector
- Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
- Coherence Depletion in Quantum Algorithms
- Deterministic quantum search with adjustable parameters: implementations and applications
- Maximally entangled state and fully entangled fraction
- Quantum coherence fraction
- Complementarity between Success Probability and Coherence in Grover Search Algorithm
- Algebraic analysis of quantum search with pure and mixed states
- Device-independent Verification of Quantum Coherence without Quantum Control