REVIEW 27 cited by
Quantum algorithms: A survey of applications and end-to-end complexities
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
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
Forward citations
Cited by 27 Pith papers
-
Unfolded distillation: very low-cost magic state preparation for biased-noise qubits
Unfolded distillation prepares an |X^{1/4}> magic state with logical error 3e-7 using 53 biased-noise qubits and 5.5 rounds, by unfolding the 3D Reed-Muller X-stabilizers into a 2D layout.
-
Heisenberg limited multiple eigenvalue estimation via off-the-grid compressed sensing
Combining off-grid compressed sensing with MUSIC spectral analysis estimates multiple molecular eigenvalues from few Hadamard-test samples with numerical Heisenberg-limited scaling.
-
QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
QKAN is a quantum algorithmic framework using block-encodings and QSVT to implement wide-and-shallow networks for quantum learning and compositional state preparation.
-
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/ε).
-
High-level quantum structured programs as quantum registers compositions
A formal framework for structured quantum programming where operations act on entire quantum registers, demonstrated by a quantum SMT solver prototype.
-
Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics
DQMW-Sample realizes a classically hard online learning primitive via dissipative quantum dynamics with sublinear regret and proven hardness for classical simulation including PH collapse.
-
Fermionic Hamiltonian engineering with local control
Linear-programming method for conjugating local fermionic unitaries with free evolution realizes arbitrary complex tunneling coefficients in fermionic lattice models constrained only by connectivity.
-
Hamiltonian dynamics from pure dissipation
Purely dissipative Lindbladians without Hamiltonian part can approximate unitary dynamics to ε error in diamond norm with O(t²/ε) time, which is optimal for time-independent cases.
-
Phase-Stable Hologram Updates for Large-Scale Neutral-Atom Array Reconfiguration
WPGS algorithm enforces inter-frame phase continuity in holographic tweezers to suppress refresh-induced atom loss and speed up updates for large neutral-atom arrays.
-
Quantum phase estimation with optimal confidence interval using three control qubits
A DPSS control state for optimal-confidence quantum phase estimation can be approximated by a bond-dimension-4 matrix product state and prepared with only three recycling control qubits.
-
Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization
Precomputed embeddings reduce the preprocessing overhead of a quantum-annealer-based Benders decomposition by about an order of magnitude on small transmission-network expansion problems, with no loss in solution quality.
-
Adiabatic preparation of thermal states and entropy-noise relation on noisy quantum computers
Adiabatic evolution prepares local thermal states from initial Gibbs states while conserving entropy density in the thermodynamic limit, with mirror-circuit benchmarking of hardware noise entropy demonstrated experime...
-
Distributed fault-tolerant quantum memories over a 2xL array of qubit modules
BB codes can be measured with constant-depth syndrome extraction in a 2 by L module array with a cyclic shift, and the 144-qubit BB code reaches simulated logical error rates below 2e-6 at physical error rate 1e-3.
-
Quantum Internet in a Nutshell -- Advancing Quantum Communication with Ion Traps
A trapped-ion quantum computer emulates BB84 and BBM92 with cloning and side-channel attacks, and simulated small QEC codes can suppress channel noise and fingerprint the noise channel.
-
Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
Progressive widening MCTS with sampling action space automates quantum circuit design, cutting evaluations 10-100x and CNOT gates up to 3x versus prior MCTS on chemistry and linear-equation tasks.
-
Qiskit Code Migration with LLMs
A taxonomy-guided RAG system with LLMs reduces hallucinations and improves migration suggestions for Qiskit code compared to unconstrained retrieval.
-
Analog photonic simulator for large-scale transport
Continuous-variable photonic platform with 20,000-mode cluster state simulates advection transport equation, achieving relative errors of 0.8% and 0.92% on first- and second-order moments via homodyne readout.
-
Fault-tolerant interfaces for modular quantum computing on diverse qubit platforms
Comparative analysis of fault-tolerant interfaces for modular quantum computing using surface codes, including novel grow-and-distil protocols, to determine optimal strategies across hardware parameters for low logica...
-
Ground and excited-state energies with analytic errors and short time evolution on a quantum computer
The paper proposes quantum prolate diagonalization for simultaneous ground and excited state energy estimation, claiming chemical accuracy at the Heisenberg limit, but the scaling evidence is not self-contained.
-
Linearization Scheme of Shallow Water Equations for Quantum Algorithms
A Carleman linearization maps 1D shallow water equations to a linear system for quantum solvers, but validation is limited to small-amplitude test cases and the speedup remains conditional.
-
Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions
Linear PDEs with Robin boundary conditions can be simulated with explicit oracle-free quantum circuits whose gate count grows polynomially in grid size and linearly in dimension.
-
Mind the gaps: The fraught road to quantum advantage
The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.
-
The vast world of quantum advantage
Assuming quantum computers are strictly more powerful than classical ones, the problem of deciding whether a given quantum circuit beats a specific classical simulation heuristic is solvable by quantum computers but n...
-
Quantum Simulation and Optimization of Water Distribution Networks
On small water distribution networks, a quantum-classical hybrid using VQLS reproduces EPANET pressures and flows, while HHL fails and quantum annealing gives only approximate results.
-
Mind the gaps: The fraught road to quantum advantage
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
-
Procedural Generation and Games at the Dawn of Fault Tolerant Quantum Computing
A vision paper arguing procedural content generation is a promising early application of fault-tolerant quantum computing, illustrated by a game concept that uses a quantum algorithm for the Jones polynomial.
-
Quantum Computing Technology Roadmaps and Capability Assessment for Scientific Computing -- An analysis of use cases from the NERSC workload
A NERSC analysis finds that more than 50% of its workload could ultimately benefit from quantum computing and that vendor roadmaps and quantum application requirements are projected to overlap in the next 5 to 10 years.
Discussion (0). Sign in to comment.