A Quantum Algorithm for Finding the Minimum
read the original abstract
We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.
This paper has not been read by Pith yet.
Forward citations
Cited by 20 Pith papers
-
Constraint-Aware Quantum Optimization of Defect Configurations in Doped ZrO2: XY-Mixer QAOA and Grover Adaptive Search
Presents an end-to-end constraint-aware quantum optimization pipeline using XY-mixer QAOA and Grover Adaptive Search for low-energy defect configurations in doped ZrO2, with QAOA validated against exact enumeration on...
-
Towards Implementable Quantum Divide and Conquer: A TSP Solver with Improved Exponential Base over Held-Karp
A parameterized quantum divide-and-conquer TSP solver achieves O*(1.865666…^n) query complexity via 4-subset partitioning and a new set-partition state preparation method, correcting prior work to show no quantum adva...
-
Quantum enhanced rare event discovery and sampling
A quantum algorithm discovers and samples rare events with optimal quantum scaling without prior knowledge of the events, yielding quadratic speedup for heavy-tailed systems and polynomial speedup for stationary processes.
-
Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems
A coherent quantum rollout oracle is built from O(Nw)-gate rank-select circuits with proven optimality, delivering O(sqrt(k)/eps) query complexity for planning problems and formally verified in Lean.
-
Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search
Riemannian modified Newton optimization on quantum search achieves quadratic convergence and O(√(N/M) log log(1/ε)) complexity when M/N is known.
-
Quantum-Accelerated Self-Consistent Field: A Hybrid Algorithm
GAS-SCF uses Grover adaptive search and quantum arithmetic to mark and amplify improving Fock states, offering a theoretical quadratic speedup for SCF optimization, shown via classical simulations up to 26 qubits and ...
-
Coupling-Grouped XY-QAOA for Joint Anomaly-Feature Selection
Coupling-Grouped XY-QAOA enables joint anomaly-feature selection via a constraint-preserving grouped-angle QAOA variant, achieving 45.9-61.3% circuit depth reduction and larger feasible executions (64 qubits at p=2) o...
-
Efficient and Expressive Boundary Conditions in Quantum Lattice Boltzmann Methods
New boundary condition approach for QLBM using one coherent operation on the full boundary, claimed to use fewer resources asymptotically and practically for bounce-back and specular reflection.
-
BoolXLLM: LLM-Assisted Explainability for Boolean Models
BoolXLLM augments an existing Boolean rule learner with LLMs for feature selection, discretization thresholds, and natural-language rule translation to improve interpretability while preserving accuracy.
-
Exponential-time quantum algorithms for graph coloring problems
Quantum algorithms achieve O(1.9140^n) time for chromatic number with QRAM and O(1.9575^n) for 20-coloring in polynomial space by combining quantum dynamic programming with Grover search on branching algorithms.
-
CARVE-Q: Quantum-Proposed, Classically Certified Interactive Driving Repair
CARVE-Q applies Durr-Hoyer quantum minimum finding to a black-box repair lattice in interactive driving while preserving classical verifier authority for certificates.
-
Energy-selective quantum search with Ising Hamiltonian phase oracles
The work shows that Ising Hamiltonian phase oracles enable energy-selective quantum search with Grover-type amplification, achieving standard quadratic scaling for Gaussian spectra and proposing corrections for random...
-
Quantum-Native Maximum Likelihood Detection in Random Access Channel with Overloaded MIMO
A quantum-native MLD detector using Grover adaptive search with search space reduction achieves optimal performance in overloaded MIMO random access channels while cutting Grover rotations by up to 65%.
-
Explicit Quantum Search Algorithm for the Densest k-Subgraph Problem
Explicit gate-based Grover oracle for densest k-subgraph using Dicke states and QFT for edge counting, shown via numerical simulations to give quadratic speedup over brute force.
-
Machine learning methods in quantum computing theory
Authors present a multiclass tree tensor network algorithm demonstrated on IBM quantum processor and a neural network approach for noise-robust quantum state tomography.
-
Quantum iterative approach to the Traveling Salesman Problem
The paper outlines a quantum framework combining QPE and Grover-style amplification for TSP, demonstrates it on a small instance, and gives an expected complexity scaling with error tolerance epsilon.
-
Quantum Model for CVRPTW
A Grover-search-based quantum model for CVRPTW that encodes constraints with only linear additional decision qubits relative to TSP formulations.
-
Towards Quantum Optimised Malware Containment
A hybrid quantum approach is proposed to achieve quadratic speedups in influence estimation and edge removal optimization for malware containment modeled as a network influence minimisation problem.
-
A Quantum Algorithm for Finding $k$-Minima
Quantum algorithm for k-minima with O(sqrt(k N)) query complexity via threshold search and generalized amplitude amplification.
-
Setting angles in quantum approximate optimization at utility-scale
The paper benchmarks approximation techniques and transfer learning for setting QAOA angles at utility scale and extracts operational guidance from hardware-validated results.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.