REVIEW 24 cited by
A fast quantum mechanical algorithm for database search
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 24 Pith papers
-
Quantum Approximate Counting, Simplified
Quantum approximate counting can match the optimal query complexity without the quantum Fourier transform, using only Grover iterations and classic coin-estimation analysis.
-
Non-Hermitian Quantum Adiabatic Algorithm
A history-decoupled Hamiltonian mapping makes non-Hermitian adiabatic quantum optimization pseudospectrally stable, achieving polynomial-time (per configuration) evolution on the CK maximum-independent-set benchmarks.
-
BPBO: Blindness-Preserving Brickwork Optimization by Certified Region Resynthesis
BPBO performs certified local resynthesis on one- to three-wire regions of BFK09 brickwork to reduce pattern size while preserving UBQC blindness, demonstrated on Grover and Toffoli cases with reductions up to 3x725 to 3x98.
-
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.
-
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/ε).
-
Closed Timelike Curve Decoding on Quantum Hardware
Routing a Deutsch-CTC loop state to a dump register makes the induced map the replacement channel σ ↦ ρ_M with unique fixed point ρ_M; IBM single-qubit data characterize the post-selected decoder branch.
-
A Quantum-Classical Surrogate Model for the Collision Operator of the Lattice Boltzmann Method
A quantum machine learning surrogate based on parameterized circuits with data re-uploading approximates the full BGK collision dynamics in LBM across all admissible relaxation parameters and is validated on Taylor-Gr...
-
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.
-
Quantum speedup from nonclassical polarization
For cross-Kerr interactions, the unrestricted quantum speed limit exceeds the speed limit of classical angular-momentum-coherent-state dynamics by a ratio that grows as √N, quantifying polarization nonclassicality as ...
-
Quantum entanglement provides a competitive advantage in adversarial games
Entangled 8-qubit PQC feature extractors in PPO agents for Pong consistently beat separable PQCs of similar size and can match or exceed small classical MLPs in the low-parameter regime.
-
Efficient certification of intractable quantum states with few Pauli measurements
The paper claims Clifford-enhanced product states can be certified with O(n^2/epsilon^2) Pauli measurements in the i.i.d. setting and polynomially many in the adversarial setting, but the central estimator is derived ...
-
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.
-
Supervised learning with a quantum classifier using a multi-level system
A variational quantum classifier that encodes features into a single N-level quantum system and trains all samples of a class at once via a density-matrix loss, achieving moderate accuracy on four benchmark datasets.
-
Effect of isotropic errors on the complexity of Grover's algorithm
Numerical simulations indicate isotropic errors degrade Grover's algorithm performance and success probability on noisy quantum hardware.
-
Eigenstate Preparation on Quantum Computers
A dissertation presenting adiabatic evolution with optimal control, the Rodeo Algorithm, and a new Variational Rodeo Algorithm that uses Rodeo success probability as a variational cost function.
-
Answer Partitions and Oracle Access Determine Quantum Query Complexity
The abstract and full text of arXiv:2605.12675 describe different papers; the abstract's partition-query classification is absent from the v3 text, which is a clarificatory essay with a correct but routine which-path-...
-
Numerical Experiments with Parameter Setting of Trotterized Quantum Phase Estimation for Quantum Hamiltonian Ground State Computation
On a 3-qubit Heisenberg spin glass, Trotterized QPE samples the ground-state-energy phase at a rate fixed by initial-state overlap times the textbook QPE success probability, saturating at surprisingly high Trotter error.
-
Towards Continuous-variable Quantum Neural Networks for Biomedical Imaging
A 4-qumode Gaussian CV-QNN classifies MedMNIST images with accuracy statistically indistinguishable from a 42-parameter classical linear model and a DV-QNN.
-
Mid-circuit measurement as an algorithmic primitive
A single-ancilla Hadamard test post-selects a QAOA state toward low-energy answers, but the implementation sets its parameters from the exact ground energy, making the convergence demonstration self-referential.
-
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.
-
Quantum-Kit: Simulating Shor's Factorization of 24-Bit Number on Desktop
The authors report that their Quantum-Kit simulator factorized the 24-bit integer 13,564,597 in about 26 minutes on a single-core desktop using Kitaev's one-qubit-recycling version of Shor's algorithm.
-
Quantum Approximate Optimisation Applied to Graph Similarity
A QAOA simulation study of graph similarity through edge overlap finds that a compact encoding with many infeasible states causes QAOA to underperform random sampling as graphs grow.
Discussion (0). Continue with ORCID to comment.