REVIEW 16 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 16 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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Towards reliable quantum software, algorithm and use-case development: Multidisciplinary analysis from the perspective of Finnish industries
A Finnish project synthesis recommends early investment in quantum-classical software capabilities, focusing on optimization and simulation, with a timeline to 2035 based on vendor roadmaps.
-
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.
-
Quantum Algorithm Software for Condensed Matter Physics
A review of quantum algorithm software that advertises a benchmark suite, yet the body contains no benchmarks, data, or code.
Discussion (0). Sign in to comment.