Nested quantum search and NP-complete problems

Abstract

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d}$, where $d$ is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d)$. It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting this standard search algorithm. The number of iterations required to find the solution of an average instance of a constraint satisfaction problem scales as $\sqrt{d^{\alpha }}$, with a constant $\alpha <1$ depending on the nesting depth and the problem considered. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, this constant $\alpha$ is estimated to be around 0.62 for average instances of maximum difficulty. This corresponds to a square-root speedup over a classical nested search algorithm, of which our presented algorithm is the quantum counterpart.

18 pages RevTeX, 3 Postscript figures

References in corpus (7)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Computation and Decision Trees
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• A Framework for Structured Quantum Search
• Quantum Mechanical Square Root Speedup in a Structured Search Problem

Cited by in corpus (47)

• Quantum Search by Local Adiabatic Evolution
• Efficient Distributed Quantum Computing
• Implementation of Grover's Quantum Search Algorithm in a Scalable System
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Time-efficient implementation of quantum search with qudits
• The effect of unitary noise on Grover's quantum search algorithm
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Low depth mechanisms for quantum optimization
• Probabilistic Nonunitary Gate in Imaginary Time Evolution
• Generalized Quantum Search with Parallelism
• Quantum walk speedup of backtracking algorithms
• Adiabatic quantum search algorithm for structured problems
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• What is a quantum computer, and how do we build one?
• Scalable quantum search using trapped ions
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Analysis of Grover's quantum search algorithm as a dynamical system
• Quantum-accelerated constraint programming
• An Introduction to Quantum Computing for Non-Physicists
• Optimizing Gate Decomposition for High-Level Quantum Programming
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Quantum Computing for Software Engineering: Prospects
• Algebraic analysis of quantum search with pure and mixed states
• Magnetism, FeS colloids, and Origins of Life
• Quantum Algorithm for Lexicographically Minimal String Rotation
• A quantum algorithm for solving 0-1 Knapsack problems
• Speedup of iterated quantum search by parallel performance
• Quantum search in many-body interacting system with long-range interaction
• Single-Step Quantum Search Using Problem Structure
• ROM-based quantum computation: Experimental explorations using Nuclear Magnetic Resonance, and future prospects
• Structured quantum search in NP-complete problems using the cumulative density of states
• Universal construction for the unsorted quantum search algorithms
• Can magnetism-assisted quasiperiodic structures in Russell-FeS `bubbles' offer a quantum coherent origin of life?
• Simulation of static and random errors on Grover's search algorithm implemented in a Ising nuclear spin chain quantum computer with few qubits
• Quantum search processes in the cyclic group state spaces
• Algorithm for Finding the Maximum Clique Based on Continuous Time Quantum Walk
• Finding Solutions to NP Problems: Philosophical Difference Between Quantum and Evolutionary Search Algorithms
• The universal quantum driving force to speed up a quantum computation -- The unitary quantum dynamics
• Structured Adiabatic Quantum Search
• Efficient quantum algorithm for solving structured problems via multi-step quantum computation
• Quantum search of partially ordered sets
• Binary Subdivision for Quantum Search
• A new adiabatic quantum search algorithm
• Spatial search for a general multi-vertex state on graph by continuous-time quantum walks
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem
• A quantum search method for quadratic and multidimensional knapsack problems
• A Novel Approach to Quantum Heuristics for Structured Database Search