Recognition: unknown
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 5 Pith papers
-
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.
-
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.
-
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.
-
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...
-
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.