A fast quantum mechanical algorithm for database search
read the original abstract
Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only O(sqrt(N)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.
This paper has not been read by Pith yet.
Forward citations
Cited by 13 Pith papers
-
Ancilla-Efficient QSAMPLE Preparation for Reversible Markov Chains
A one-ancilla framework for QSAMPLE preparation via GQSP-based selective phase compilation embedded in fixed-point amplitude amplification, improving overlap dependence to inverse square-root minimum overlap.
-
Exhaustive and feasible parametrisation with applications to the travelling salesperson problem
Exhaustively parametrised feasibility-respecting quantum circuits can reach every feasible solution to problems like TSP with certainty using fixed parameters by leveraging group actions and generating sequences.
-
Efficient Simulation of High-Level Quantum Gates
A gadget-based simulator directly simulates high-level quantum gates via low-rank stabilizer decompositions of magic states, improving both theoretical complexity and practical runtime over standard compilation-based methods.
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
The relative entropy of magic and its nonadditivity
Characterizes qubit magic states via relative entropy of entanglement results and proves nonadditivity of relative entropy of magic for multi-qubit tensor products.
-
Activating entanglement and EPR steering from continuous-variable resources using witness-based measures
A witness-based framework quantifies continuous-variable resources and activates them into discrete-variable entanglement or EPR steering via measure-and-prepare channels that produce Werner states.
-
Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems
Benchmarks gradient-ascent algorithms for constrained free energy minimization on quantum Heisenberg models and stabilizer codes, with applications to thermal state design and fixed-temperature quantum encoding.
-
A resource-efficient quantum-walker Quantum RAM
Proposes a quantum-walker qRAM on a single binary tree using local operations that reduces resources while preserving optimal query complexity.
-
Network Impact of Post-Quantum Certificate Chain sizes on Time to First Byte in TLS Deployments
Post-quantum certificate chains cause discrete jumps in TTFB once they exceed transport flight limits, with Merkle Tree Certificates supporting 2-3x larger chains than current CDN optimizations.
-
Task Scheduling Optimization with Direct Constraints from a Tensor Network Perspective
Tensor network algorithms provide exact optimal task assignments on machines under directed constraints, with preprocessing and iterative improvements to reduce complexity.
-
The Physical and Contextual Limits of Quantum Speedup
Quantum speedups arise from engineered interference in high-dimensional Hilbert spaces rather than classical branchwise parallelism, constrained by no unitary garbage erasure, contextuality, and absence of absorbing h...
-
The Physical and Contextual Limits of Quantum Speedup
Quantum speedups come from reversible embeddings and engineered interference that identify solution classes rather than from branchwise classical parallelism, subject to limits like impossible unitary garbage erasure ...
-
Quantum Decoding Algorithms: Quantum Speedups in Optimization
A review describing the Decoded Quantum Interferometry algorithm for quantum speedups in max-LINSAT optimization, with claimed superpolynomial advantage in the OPI problem.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.