Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks

Abstract

Quantum algorithms have demonstrated provable speedups over classical counterparts, yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge. In this work, we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms. We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities. These probabilities are fundamentally determined by specific initial state properties: the coherence fraction governs the first algorithm's performance, while entanglement and coherence dominate the outcomes of the second and third algorithms, respectively. We show that increased coherence fraction enhances success probability, but greater entanglement and coherence reduce it in the latter two cases. These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design. Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.

7+7 pages, 5 figures

References in corpus (51)

• Quantum entanglement
• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Mixed State Entanglement and Quantum Error Correction
• Quantum Machine Learning
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Computing
• Quantum algorithm for solving linear systems of equations
• Quantum Simulation
• Quantifying Coherence
• Quantum computational advantage using photons
• Quantifying Entanglement
• Quantum support vector machine for big data classification
• A Quantum Random Walk Search Algorithm
• Remote State Preparation
• Quantum Computational Supremacy
• Spatial search by quantum walk
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Strongly Correlated Quantum Walks in Optical Lattices
• Converting Coherence to Quantum Correlations
• Quantum coherence and geometric quantum discord
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• A quantum-inspired classical algorithm for recommendation systems
• Quantum Algorithms: Entanglement Enhanced Information Processing
• Converting Nonclassicality into Entanglement
• Faster quantum walk algorithm for the two dimensional spatial search
• Coherence depletion in the Grover quantum search algorithm
• Local environment can enhance fidelity of quantum teleportation
• The resource theory of steering
• Machine learning meets quantum physics
• Optimal Teleportation Based on Bell Measurement
• Universal quantum computation with little entanglement
• Optimized quantum random-walk search algorithms
• Maximally coherent states and coherence-preserving operations
• Quantum Walk in Momentum Space with a Bose-Einstein Condensate
• Towards quantum enhanced adversarial robustness in machine learning
• Quantum Neural Network for Quantum Neural Computing
• Catalytic quantum teleportation and beyond
• Differential Evolution for Many-Particle Adaptive Quantum Metrology
• On the Role of Coherence in Shor's Algorithm
• An entanglement monotone derived from Grover's algorithm
• Optimal quantum spatial search on random temporal networks
• A new coherence measure based on fidelity
• Connecting velocity and entanglement in quantum walks
• Quantum Algorithm for Approximating Maximum Independent Sets
• Quantum coherence fraction
• Deterministic spatial search using alternating quantum walks
• Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
• Coherence Fraction in Grover Search Algorithm
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Implementing arbitrary quantum operations via quantum walks on a cycle graph