Optimization of probabilistic quantum search algorithm with a priori information
arXiv:2304.02856 · doi:10.1103/PhysRevA.108.022417
Abstract
A quantum computer encodes information in quantum states and runs quantum algorithms to surpass the classical counterparts by exploiting quantum superposition and quantum correlation. Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. It has a quadratic reduction in the query complexity of database search, and is known to be optimal when no a priori information about the elements of the database is provided. In this work, we consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements, and minimize the number of oracle calls by optimizing the initial state of the quantum system and the reflection axis of the diffusion operator. The initial state and the reflection axis are allowed to not coincide, and thus the quantum search algorithm rotates the quantum system in a three-dimensional subspace spanned by the initial state, the reflection axis and the search target state in general. The number of oracle calls is minimized by a variational method, and formal results are obtained with the assumption of low failure probability. The results show that for a nonuniform a priori distribution of the database elements, the number of oracle calls can be significantly reduced given a small decrease in the success probability of the quantum search algorithm, leading to a lower average query complexity to find the solution of the search problem. The results are applied to a simple but nontrivial database model with two-value a priori probabilities to show the power of the optimized quantum search algorithm. The paper concludes with a discussion about the generalization to higher-order results that allows for a larger failure probability for the quantum search algorithm.
arXiv commentv2: Main text expanded to include analysis of the first-order optimization result. Close to the published version
References in corpus (37)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- A variational eigenvalue solver on a quantum processor
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum algorithm for solving linear systems of equations
- Experimental One-Way Quantum Computing
- Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
- A Quantum Random Walk Search Algorithm
- Quantum computers can search rapidly by using almost any transformation
- Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
- Grover Algorithm with zero theoretical failure rate
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Fixed-point quantum search with an optimal number of queries
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- Implementation of quantum search algorithm using classical Fourier optics
- On Arbitrary Phases in Quantum Amplitude Amplification
- Grover's search algorithm: An optical approach
- Phase matching in quantum searching
- Sliding mode control of quantum systems
- Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
- A Review on Quantum Search Algorithms
- Depth optimization of quantum search algorithms beyond Grover's algorithm
- Deterministic Grover search with a restricted oracle
- Variationally Learning Grover's Quantum Search Algorithm
- Simple Algorithm for Partial Quantum Search
- Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
- Experimental realization of a continuous version of the Grover algorithm
- A programmable three-qubit superconducting processor with all-to-all connectivity
- Error tolerance in an NMR Implementation of Grover's Fixed-Point Quantum Search Algorithm
- A Hybrid Quantum Encoding Algorithm of Vector Quantization for Image Compression
- Optimization of Partial Search
- Quest for Fast Partial Search Algorithm
- Simple implementation of a quantum search with trapped ions
- Superposing pure quantum states with partial prior information
- Experimental implementation of generalized Grover's algorithm of multiple marked states and its application
- Preparation of GHZ states via Grover's quantum searching algorithm
- Exact quantum lower bound for Grover's problem
- Invariance of success probability in Grover's quantum search under local noise with memory