A different kind of quantum search
arXiv:quant-ph/0503205 · doi:10.1103/PhysRevLett.95.150501
Abstract
The quantum search algorithm consists of an alternating sequence of selective inversions and diffusion type operations, as a result of which it can find a target state in an unsorted database of size N in only sqrt(N) queries. This paper shows that by replacing the selective inversions by selective phase shifts of Pi/3, the algorithm gets transformed into something similar to a classical search algorithm. Just like classical search algorithms this algorithm has a fixed point in state-space toward which it preferentially converges. In contrast, the original quantum search algorithm moves uniformly in a two-dimensional state space. This feature leads to robust search algorithms and also to conceptually new schemes for error correction.
13 pages, 4 figures
References in corpus (2)
Cited by in corpus (81)
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Fixed-point quantum search with an optimal number of queries
- Quantum Computing with NMR
- Quantum Copy-Protection and Quantum Money
- The methodology of resonant equiangular composite quantum gates
- Quantum Algorithm for Linear Regression
- Noisy intermediate-scale quantum computers
- Speed-up via Quantum Sampling
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Accuracy vs run time in adiabatic quantum search
- Duality and Recycling Computing in Quantum Computers
- Quantum Speed-up for Approximating Partition Functions
- The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
- A quantum genetic algorithm with quantum crossover and mutation operations
- Probabilistic Nonunitary Gate in Imaginary Time Evolution
- Scale invariance of entanglement dynamics in Grover's quantum search algorithm
- Critically damped quantum search
- Geometric Algebra and Information Geometry for Quantum Computational Software
- Quantum Searching via Entanglement and Partial Diffusion
- Sampling on NISQ Devices: "Who's the Fairest One of All?"
- Multi-phase matching in the Grover algorithm
- Dynamic Grover Search: Applications in Recommendation systems and Optimization problems
- Repeat-Until-Success circuits with fixed-point oblivious amplitude amplification
- Fixed-Point Adiabatic Quantum Search
- Generalized Grover's algorithm for multiple phase inversion states
- Threshold-Based Quantum Optimization
- An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq
- Steering Quantum Dynamics via Bang-Bang Control: Implementing optimal fixed point quantum search algorithm
- Faster quantum mixing for slowly evolving sequences of Markov chains
- Decrease of Fisher information and the information geometry of evolution equations for quantum mechanical probability amplitudes
- Parasitic Photon-Pair Suppression via Photonic Stop-Band Engineering
- Effect of system level structure and spectral distribution of the environment on the decoherence rate
- Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Improved Bounds for Eigenpath Traversal
- Quantum Amplitude Amplification Operators
- Fixed-point Quantum Search for Different Phase Shifts
- A Query-based Quantum Eigensolver
- Fair Sampling Error Analysis on NISQ Devices
- Non adiabatic quantum search algorithms
- Weakly measured while loops: peeking at quantum states
- Tree Search and Quantum Computation
- Improved amplitude amplification strategies for the quantum simulation of classical transport problems
- Fixed Phase Quantum Search Algorithm
- Simulated Quantum Computation of Global Minima
- Amplitude Amplification for Optimization via Subdivided Phase Oracle
- Code Generator for Quantum Simulated Annealing
- Automatic Post-selection by Ancillae Thermalisation
- An Adaptive, Fixed-Point Version of Grover's Algorithm
- A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation
- Quantum Dynamic Programming
- Information Geometric Aspects of Probability Paths with Minimum Entropy Production for Quantum State Evolution
- Performance of Equal Phase-Shift Search for One Iteration
- On Quantum Circuits for Discrete Graphical Models
- Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
- Fixed-point quantum continuous search algorithm with optimal query complexity
- Modular quantum signal processing in many variables
- An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
- Complementary-multiphase quantum search for all numbers of target items
- Design for implementation of discrete-time quantum walk with circulant matrix on graph by optical polarizing elements
- Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
- Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
- Quantum Algorithms with Fixed Points: The Case of Database Search
- Solving mathematical problems with quantum search algorithm
- A Fast fixed-point Quantum Search Algorithm by using Disentanglement and Measurement
- A Fast Measurement based fixed-point Quantum Search Algorithm
- Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma
- Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
- Constant-Time Quantum Algorithm For The Unstructured Search Problem
- Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
- Optimization of the damped quantum search
- Binary Subdivision for Quantum Search
- Quantum Search with Prior Knowledge
- Multi-Qubit Dynamical Quantum Search Algorithm with Dissipation
- Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
- Parameter security characterization of knapsack public-key crypto under quantum computing
- Explicit decoders using fixed-point amplitude amplification based on QSVT
- Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q
- Quantum spatial best-arm identification via quantum walks
- Reasoning about Recursive Quantum Programs