A Topological Oracle Model for Proving P ≠ NP
1996/05/29 by Grover, Lov K. · 256 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #DNA and Biological Computing #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.quant-ph/9605043
openalex publication_date 1996/05/29 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
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.
Citations
Cited by
- Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer
- Performance Analysis of QAOA Across Distributed Quantum Network Topologies Using SwitchQNet
- Recoverable Quantum Computation: An Information-Centric Paradigm for Quantum Computing with Errors
- Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization
- Architecture-aware Unitary Synthesis
- Solving Segment Display Problems Using Quantum Grover's Search Algorithm
- Quantum-Resistant Cryptographic Models for Next-Gen Cybersecurity
- DeepQuantum: A PyTorch-based Software Platform for Quantum Machine Learning and Photonic Quantum Computing
- Photonic variational quantum eigensolver for NISQ-compatible quantum technology
- Protecting Quantum Circuits Through Compiler-Resistant Obfuscation
- Quantum hash function using discrete-time quantum walk on Hanoi network
- Hermitian Hulls of Rational Algebraic Geometry Codes and Applications in Quantum Codes
- Amplitude-amplified coherence detection and estimation
- Universal Blind Quantum Computation with Recursive Rotation Gates
- QuantGraph: A Receding-Horizon Quantum Graph Solver
- Thermodynamic Focusing for Inference-Time Search: Practical Methods for Target-Conditioned Sampling and Prompted Inference
- Quantum Resource Analysis of Low-Round Keccak/SHA-3 Preimage Attack: From Classical 257.8 to Quantum 228.9 using Qiskit Modeling
- Quantum Disruption: An SOK of How Post-Quantum Attackers Reshape Blockchain Security and Performance
- Dual-Qubit Hierarchical Fuzzy Neural Network for Image Classification: Enabling Relational Learning via Quantum Entanglement
- Quantigence: A Multi-Agent AI Framework for Quantum Security Research
- Scalable Quantum Error Mitigation with Neighbor-Informed Learning
- TreeVQA: A Tree-Structured Execution Framework for Shot Reduction in Variational Quantum Algorithms
- NetQMPI: An MPI-Inspired library for programming Distributed Quantum Applications over Quantum Networks using NetQASM SDK
- Topology-Guided Quantum GANs for Constrained Graph Generation
- Quantum-Amplified M/G/1/K Simulation: A Comparator-Controlled Framework for Arbitrary Service Distributions
- True Random Number Generators on IQM Spark
- Quantum Algorithm for Estimating Ollivier-Ricci Curvature
- Quantum simulation in the entanglement picture
- SAQ: Stabilizer-Aware Quantum Error Correction Decoder
- A Grover-compatible manifold optimization algorithm for quantum search
- Constraint-oriented biased quantum search for general constrained combinatorial optimization problems
- Wavelet-Accelerated Physics-Informed Quantum Neural Network for Multiscale Partial Differential Equations
- Security Analysis of Integer Learning with Errors with Rejection Sampling
- Quantum Interior Point Methods: A Review of Developments and An Optimally Scaling Framework
- Constraint-oriented biased quantum search for linear constrained combinatorial optimization problems
- Dequantizing Short-Path Quantum Algorithms
- Towards Quantum Stochastic Optimization for Energy Systems under Uncertainty: Joint Chance Constraints with Quantum Annealing
- Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle
- Quantum Hash Function Based on Spectral Properties of Graphs and Discrete Walker Dynamics
- Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
- Constraint-Optimal Driven Allocation for Scalable QEC Decoder Scheduling
- Superchannel without Tears: A Generalized Occam's Razor for Quantum Processes
- Information-Theoretic Constraints on Variational Quantum Optimization: Efficiency Transitions and the Dynamical Lie Algebra
- Resource Estimation for VQE on Small Molecules: Impact of Fermion Mappings and Hamiltonian Reductions
- From Betti Numbers to Persistence Diagrams: A Hybrid Quantum Algorithm for Topological Data Analysis
- Opportunities and Challenges for Data Quality in the Era of Quantum Computing
- Quantum-Resistant Authentication Scheme for RFID Systems Using Lattice-Based Cryptography
- Engel p-adic Isogeny-based Cryptography over Laurent Series: Foundations, Security, and an ESP32 Implementation
- Parameterized Verification of Quantum Circuits (Technical Report)
- Quantum Hardware-Efficient Selection of Auxiliary Variables for QUBO Formulations
- Machine Learning by Adiabatic Evolutionary Quantum System
- Utilizing Circulant Structure to Optimize the Implementations of Linear Layers
- Orthogonal frequency-division multiplexing for simultaneous gate operations on multiple qubits via a shared control line
- Quantum-Assisted Graph Domination Games
- Fidelity-Preserving Quantum Encoding for Quantum Neural Networks
- Note on Logical Gates by Gauge Field Formalism of Quantum Error Correction
- Quantum Simulation of Non-unitary Dynamics via Contour-based Matrix Decomposition
- A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
- Quantum Meet-in-the-Middle Attacks on Key-Length Extension Constructions
- The Grand Challenge of Quantum Applications
- Efficient certification of intractable quantum states with few Pauli measurements
- Recent Advances on Nonadiabatic Geometric Quantum Computation
- Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
- Fault-Tolerant Encoding of Logical Qudits in Spin Systems
- Quantum Approximate Walk Algorithm
- Trade-off between complexity and energy in quantum phase estimation
- Distributed quantum approximate counting algorithm
- Security Evaluation of Quantum Circuit Split Compilation under an Oracle-Guided Attack
- Normalized tensor train decomposition
- Neutral-atom quantum computation using multi-qubit geometric gates via adiabatic passage
- Hybrid Quantum-Classical Detection for RIS-Assisted SC-FDE via Grover Adaptive Search
- Spectrum for a non-unitary one-dimensional two-state quantum walk with one defect
- Introducing Quantum Computing into Statistical Physics: Random Walks and the Ising Model with Qiskit
- Enhancing NTRUEncrypt Security Using Markov Chain Monte Carlo Methods: Theory and Practice
- Quantum Circuit Implementation of Two Matrix Product Operations and Elementary Column Transformations
- Towards Continuous-variable Quantum Neural Networks for Biomedical Imaging
- ECCentric: An Empirical Analysis of Quantum Error Correction Codes
- Optimal transfer of entanglement in oscillator chains in non-Markovian open systems
- Empirical Studies on Quantum Optimization for Software Engineering: A Systematic Analysis
- Characterizing Quantum Internet Using Complex Network Models
- Elliptic butterflies
- The Fast for the Curious: How to accelerate fault-tolerant quantum applications
- Variational quantum computing for quantum simulation: principles, implementations, and challenges
- Probability distribution reconstruction using circuit cutting applied to a variational classifier
- Practical Quantum Advantage before Fault Tolerance via Quantum-Informed Machine Learning
- QAFE2: Quantum accelerated multiscale finite element analysis
- Constant-Depth Unitary Preparation of Dicke States
- Quantum-Resistant Networks Using Post-Quantum Cryptography
- Optimizing Quantum Compilation via High-Level Quantum Instructions
- Future-Proofing Authentication Against Insecure Bootstrapping for 5G Networks: Feasibility, Resiliency, and Accountability
- Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows
- Parameterized quantum algorithms for closest string problems
- A Gateway to Quantum Computing for Industrial Engineering
- Q-RAN: Quantum-Resilient O-RAN Architecture
- Good quantum codes with addressable and parallelizable non-Clifford gates
- Revealing the quantum nature of memory in non-Markovian dynamics on IBM Quantum
- Collaborative penetration testing suite for emerging generative AI algorithms
- Qatsi: Stateless Secret Generation via Hierarchical Memory-Hard Key Derivation
- Achieving Sub-Exponential Speedup in Gate-Based Quantum Computing for Quadratic Unconstrained Binary Optimization
- QuanBench: Benchmarking Quantum Code Generation with Large Language Models
- Symmetric Reduction Techniques for Quantum Graph Colouring
- Teaching Quantum Computing through Lab-Integrated Learning: Bridging Conceptual and Computational Understanding
- Singularity-free dynamical invariants-based quantum control
- A Hybrid Quantum Solver for Gaussian Process Regression
- Advances in Quantum Genetic Algorithms
- Quantum Search in Superposed Quantum Lattice Gas Automata and Lattice Boltzmann Systems
- Quantum Approximate Optimization Algorithm for Maximum Likelihood Detection in Massive MIMO
- Hybrid Boson Sampling-Neural Network Architecture for Enhanced Classification
- Tight Quantum Time-Space Tradeoffs for Permutation Inversion
- On the Potential of Quantum Computing in Classical Program Analysis
- Structural encoding with classical codes for computational-basis bit-flip correction in the early fault-tolerant regime
- QLENS: Towards A Quantum Perspective of Language Transformers
- Reverse Supervision at Scale: Exponential Search Meets the Economics of Annotation
- Depth One Quantum Alternating Operator Ansatz as an Approximate Gibbs Distribution Sampler
- Verifiable blind observable estimation: A composably secure protocol for near-term quantum advantage tasks
- An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
- Measuring gravitational lensing time delays with quantum information processing
- Speed limits of two-qutrit gates
- Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
- Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models
- Integer Factoring with Unoperations
- AI-Driven Post-Quantum Cryptography for Cyber-Resilient V2X Communication in Transportation Cyber-Physical Systems
- Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms
- End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
- Spin quantum computing, spin quantum cognition
- Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit
- Mirrored Entanglement Witnesses for Multipartite and High-Dimensional Quantum Systems
- Reproducible Builds for Quantum Computing
- Fast-forwardable Lindbladians imply quantum phase estimation
- Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems
- Communication-Optimal Blind Quantum Protocols
- Quantum Algorithm for Binary Vector Encoding and Retrieval Utilizing the Permutation Trick
- 3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: O(2(n)/(2)) Algorithm Is Nearly Optimal under QSETH
- Qudit low-density parity-check codes
- Recent quantum runtime (dis)advantages
- Quantum Lattice Boltzmann Method for Multiple Time Steps Without Reinitialization for Linear Advection-Diffusion Problems
- A New Quantum Linear System Algorithm Beyond the Condition Number and Its Application to Solving Multivariate Polynomial Systems
- Quantum walks through generalized graph composition
- Quantum walk search based edge detection of images
- Rethinking Services in the Quantum Age: The SOQ Paradigm
- C2|Q>: A Robust Framework for Bridging Classical and Quantum Software Development
- Pre-Distillation of Magic States via Composite Schemes
- Stab-QRAM: An All-Clifford Quantum Random Access Memory for Special Data
- Toward Quantum-Enabled Biomarker Discovery: An Outlook from Q4Bio
- The Quantum Decoding Problem : Tight Achievability Bounds and Application to Regev's Reduction
- Mapping Quantum Threats: An Engineering Inventory of Cryptographic Dependencies
- Linear Regression in p-adic metric spaces
- Quantum topological data analysis algorithm for dynamical systems
- Towards reconstructing quantum structured light on a quantum computer
- Optimizing the non-Clifford-count in unitary synthesis using Reinforcement Learning
- Optimal phase change for a generalized Grover's algorithm
- A Quantum Algorithm For Computing Contextuality Bounds
- Nontrivial multi-product commutation relation for reducing T-count in sequential Pauli-based computation
- Exploring the use of quantum computing for facilitating spatially and temporally resolved models of a biological cell
- Möbius-Guided Diagonal-Gate Compilation with Native Multiqubit Controlled-Phase Gates on Neutral-Atom Processors
- A CPU+DCU Heterogeneous Parallel Framework for Post-Processing Reconstruction in Quantum Circuit Cutting
- Nearly optimal quantum circuits for Boolean oracles
- Hayden--Preskill recovery at finite temperature on a quantum processor: dynamics and initial state from the SYK model
- Intro2QC: An Approachable Introduction to Quantum Computing for STEM Education in High Schools
- Closed Timelike Curve Decoding on Quantum Hardware
- Quantum Attacks Targeting Nuclear Power Plants: Threat Analysis, Defense and Mitigation Strategies
- Steiner Traveling Salesman Problem with Time Windows and Pickup-Delivery: integrating classical and quantum optimization
- Compressed Permutation Oracles
- Quantum Random Synthetic Skyrmion Texture Generation, a Qiskit Simulation
- Connecting Quantum Computing with Classical Stochastic Simulation
- Auxiliary-Qubit-Free Quantum Approximate Optimization Algorithm for the Minimum Dominating Set Problem
- Quantum-Accelerated Solution of Nonlinear Equations from Variational Principles
- Scalable Quantum Reinforcement Learning on NISQ Devices with Dynamic-Circuit Qubit Reuse and Grover Optimization
- Future-Proofing Cloud Security Against Quantum Attacks: Risk, Transition, and Mitigation Strategies
- Distributed Implementation of Variational Quantum Eigensolver to Solve QUBO Problems
- Quantum eigenpair solver with minimal sampling overhead
- Limitation of Stoquastic Quantum Annealing: A Structural Perspective
- ChipmunkRing: A Practical Post-Quantum Ring Signature Scheme for Blockchain Applications
- A Tight Quantum Algorithm for Multiple Collision Search
- Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing
- Quantum Resource Management in the NISQ Era: Challenges, Vision, and a Runtime Framework
- Multi-Partitioned Meshfree Quantum Finite Particle Method: A Hybrid Quantum Framework for Fluid Flow
- Gradients, parallelism, and variance of quantum estimates
- Requirements for Early Quantum Utility and Quantum Utility in the Capacitated Vehicle Routing Problem
- Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers
- Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties
- Observing Spacetime
- Optimal detection of quantum states via projective measurements
- Enhancing Sum Capacity via Quantum and No-Signaling Cooperation Between Transmitters
- QCardEst/QCardCorr: Quantum Cardinality Estimation and Correction
- Cross-Resonant Gates in Hybrid Fluxonium-Transmon Systems
- Universality of a standard two-qubit gate by catalytic embedding
- From Classical Data to Quantum Advantage -- Quantum Policy Evaluation on Quantum Hardware
- Quantum Machine Learning and Grover's Algorithm for Quantum Optimization of Robotic Manipulators
- Nested Grover's Algorithm for Tree Search
- Super-Quadratic Quantum Speed-ups and Guessing Many Likely Keys
- The Efficiency Frontier: Classical Shadows versus Quantum Footage
- Efficient QKD in Non-Ideal Scenarios with User-Defined Output Length Requirements
- A Framework for Quantum Data Center Emulation Using Digital Quantum Computers
- Forecasting Low-Dimensional Turbulence via Multi-Dimensional Hybrid Quantum Reservoir Computing
- LATTE: A Decoding Architecture for Quantum Computing with Temporal and Spatial Scalability
- An experience-based classification of quantum bugs in quantum software
- Accelerating BP-based decoders for QLDPC Codes with Local Syndrome-Based Preprocessing
- CNOT Oriented Synthesis for Small-Scale Boolean Functions Using Spatial Structures of Parallelotopes
- Efficient Maximum Clique Detection via Grover's Algorithm with Real-time Global Size Tracking
- A Survey of Post-Quantum Cryptography Support in Cryptographic Libraries
- Traq: Estimating the Quantum Cost of Classical Programs
- Quantum Machine Learning Applied to the Sinking of the Titanic
- QUAV: Quantum-Assisted Path Planning and Optimization for UAV Navigation with Obstacle Avoidance
- Quantum Leap in Finance: Economic Advantages, Security, and Post-Quantum Readiness
- Realization of an untrusted intermediate relay architecture using a quantum dot single-photon source
- Generalized quantum singular value transformation with application in quantum bi-conjugate gradient method
- Introducing the Quantum Economic Advantage Online Calculator
- Enhanced Rényi Entropy-Based Post-Quantum Key Agreement with Provable Security and Information-Theoretic Guarantees
- Towards quantum topological data analysis: torsion detection
- Optimizing Compilation for Distributed Quantum Computing via Clustering and Annealing
- Private Quantum Database
- Iterative Partition Search Variational Quantum Algorithm for Solving Shortest Vector Problem
- Quantum-Circuit-Based Visual Fractal Image Generation in Qiskit and Analytics
- Vectorized Attention with Learnable Encoding for Quantum Transformer
- Multi-player conflict avoidance through entangled quantum walks
- Roadblocks and Opportunities in Quantum Algorithms -- Insights from the National Quantum Initiative Joint Algorithms Workshop, May 20--22, 2024
- PennyLane-Lightning MPI: A massively scalable quantum circuit simulator based on distributed computing in CPU clusters
- Quantum Relational Knowledge Distillation
- Passive Hack-Back Strategies for Cyber Attribution: Covert Vectors in Denied Environment
- The Evolution of IBM's Quantum Information Software Kit (Qiskit): A Review of its Applications
- The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
- Unveiling the link between quantum ghost imaging and Grover's quantum searching algorithm
- Generating Compilers for Qubit Mapping and Routing
- Decoded Quantum Interferometry Under Noise
- Simulating Mass-Dependent Decoherence in Quantum Computers: Baseline Signatures for Testing Gravity-Induced Collapse
- On the role of overparametrization in Quantum Approximate Optimization
- Surpassing the PLOB bound in continuous-variable quantum secret sharing using a state-discrimination detector
- Préface
- MPS-JuliQAOA: User-friendly, Scalable MPS-based Simulation for Quantum Optimization
- A Comparative Performance Evaluation of Kyber, sntrup761, and FrodoKEM for Post-Quantum Cryptography
- Expressivity Limits in Quantum Walk-based Optimization
- Quantum Algorithms for Finite-horizon Markov Decision Processes
- Modular Quantum Amplitude Estimation: A Scalable and Adaptive Framework
- Noisy Quantum Simulation Using Tracking, Uncomputation and Sampling
- Quantum Resource Management in the NISQ Era: Implications and Perspectives from Software Engineering
- Hybrid Quantum--Classical Machine Learning Potential with Variational Quantum Circuits
- Tight Quantum-Security Bounds and Parameter Optimization for SPHINCS+ and NTRU
- Compositional Quantum Control Flow with Efficient Compilation in Qunity
- A resource-efficient quantum-walker Quantum RAM
- Solving Markov Chains with Analog Quantum Computing: The Fine Print
- Performance and Storage Analysis of CRYSTALS Kyber as a Post Quantum Replacement for RSA and ECC
- Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis
- Blockchain security based on cryptography: a review
- An Unconditionally Secure Encryption Scheme for IoBT Networks
- Evaluating Angle and Amplitude Encoding Strategies for Variational Quantum Machine Learning: their impact on model's accuracy
- Quantum Key-Recovery Attacks on FBC Algorithm
- Towards Efficient Verification of Computation in Quantum Devices
- Are controlled unitaries helpful?
- Amplitude amplification and estimation require inverses
- Enhanced Extrapolation-Based Quantum Error Mitigation Using Repetitive Structure in Quantum Algorithms
- Universal tradeoff relations between resource cost and irreversibility of channels: General-resource Wigner-Araki-Yanase theorems and beyond
- Minimizing entanglement entropy for enhanced quantum state preparation
- A Grover-Based Quantum Algorithm for Solving Perfect Mazes via Fitness-Guided Search
- Quantum circuit evolutionary framework applied on set partitioning problem
- Distinguishing Quantum Software Bugs from Hardware Noise: A Statistical Approach
Related