Source-linked AI summary
Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage
Torsten Hoefler, Thomas Haener, Matthias Troyer
TL;DR
The paper asks which proposed quantum applications can realistically offer practical advantage when asymptotic speedups alone omit computational constants. It develops guidelines to classify applications and concludes that quadratic speedups are insufficient, while small-data problems with exponential speedups—especially in chemistry and materials science—are promising.
Problem
Which proposed quantum applications can realistically offer practical advantage remains an open question, and assessing asymptotic speedups without computational constants is insufficient.
Source: p. 2Method
The paper uses a work-depth performance model to establish quantum-practicality guidelines and classify proposed applications by their potential for practical advantage.
Source: pp. 2–3Results
The analysis concludes that quadratic speedups are insufficient for practical quantum advantage and that exponential-speedup quantum-system simulations are among the most likely applications to achieve it.
Source: p. 4Takeaways & Limitations
The authors identify small-data problems with exponential speedups, especially in chemistry and materials science, as the most promising candidates for quantum practicality.
Source: p. 4The analysis assumes an optimistic hypothetical quantum computer and errs pessimistically for classical computing, comparing it with a single classical chip.
Source: p. 2
Abstract
from arXiv · showhide
Quantum computers offer a new paradigm of computing with the potential to vastly outperform any imagineable classical computer. This has caused a gold rush towards new quantum algorithms and hardware. In light of the growing expectations and hype surrounding quantum computing we ask the question which are the promising applications to realize quantum advantage. We argue that small data problems and quantum algorithms with super-quadratic speedups are essential to make quantum computers useful in practice. With these guidelines one can separate promising applications for quantum computing from those where classical solutions should be pursued. While most of the proposed quantum algorithms and applications do not achieve the necessary speedups to be considered practical, we already see a huge potential in material science and chemistry. We expect further applications to be developed based on our guidelines.
METHODS
The methods compare the quantum computer with a single microprocessor chip modeled on the NVIDIA A100 GPU, using its specifications as a classical reference.
METHODS
- The comparison uses a single microprocessor chip similar to the one in the NVIDIA A100 GPU.The paper uses the chip as its classical reference.Source: METHODS · p. 4
- The reference A100 chip is around 850 mm^2 and is manufactured using TSMC’s 7nm N7 silicon process.Source: METHODS · p. 4
- The A100 chip has around 54.2 billion transistors and operates at a cycle time of around 0.7 ns.Source: METHODS · p. 4
Determining peak operation throughputs
The section estimates peak throughputs for classical GPUs, specialized ASICs, and a hypothetical quantum computer across fp16, int32, and binary operations. Its estimates depend on operation-specific hardware assumptions and, for quantum multiplication, magic-state factory overhead.
Determining peak operation throughputs
- The throughput examples cover logical operations, fp16, and int32, while the methodology can also model other datatypes.For binary quantum operations, the analysis assumes two input qubits and one output qubit for a Toffoli adder, without ancillas.Source: Determining peak operation throughputs · pp. 5–6
- The A100 baseline is 195 Top/s fp16 and 9.75 Top/s int32 after halving datasheet rates that assume a 50/50 addition–multiplication mix.The datasheet also lists 4,992 Top/s binary tensor-core performance for a limited instruction set.Source: Determining peak operation throughputs · p. 5
- An A100-equivalent specialized ASIC is estimated at 0.55 fp16, 0.22 int32, and 77.4 bin Pop/s, roughly 2–15x faster than a programmable circuit.The estimate assumes a 0.7ns cycle time, 50% of chip area for control logic, and 54.2B transistors.Source: Determining peak operation throughputs · p. 5
- The quantum multiplier uses N controlled adders, with CCZ-depth and count 2N^2 and 5N−1 qubits; each CCZ factory is modeled as 77 logical qubits.The factory estimate converts 147,904 physical qubits using code distance 31, with physical gate errors of 10^-3 and circuits using approximately 10^8 CCZ states.Source: Determining peak operation throughputs · p. 5
- A 10-bit fp16 quantum multiplier reaches 10.5k op/s using 21 units, each with 200-cycle latency, on a chip with 10,000 logical qubits and a 10μs cycle time.The calculation assumes 5.5 magic-state factories per multiplier so units do not wait for state production on average; the results are summarized in Table 1.Source: Determining peak operation throughputs · pp. 5–6
A note on parallelism
The analysis assumes massively parallel, depth-one oracle execution on both computers, which the authors consider realistic because most practical oracles have low depth and can be parallelized across one chip.
A note on parallelism
- If oracle depth equals work, the comparison shifts toward quantum; at 2 GHz the modeled GPU slowdown is about 100,000 times, yet quadratic speedup still requires only several thousand fp16 operations.The authors describe this as an extremely unrealistic algorithmic worst case.Source: A note on parallelism · p. 6
Determining maximum operation counts per oracle call
The section estimates how many operations an oracle evaluation can contain while a quantum computer still beats a classical computer within a fixed runtime, assuming oracle calls account for the calculations and ignoring other quantum-machine costs.
Determining maximum operation counts per oracle call
- Within 10^6 seconds, the assumed classical and quantum operation capacities are 0.55 fp16 versus 7, 0.22 int32 versus 4, and 77.4 bin Zop versus 2,350 Gop, respectively.The comparison assumes all calculations are used in quantum-computer oracle calls and ignores further quantum-machine costs.Source: Determining maximum operation counts… · p. 6
- For an oracle requiring M operations per call and N invocations, the modeled runtimes are T_c = N^k · M · t_c classically and T_q = N · M · t_q quantumly.Here t_c and t_q are the respective times to evaluate an operation; the model considers polynomial X^k speedups, including Grover’s k = 2 example [12].Source: Determining maximum operation counts… · p. 6
- The maximum practical oracle size is determined by requiring the quantum runtime to be both shorter than the classical runtime and within 10^6 seconds.Although quantum computers are asymptotically faster in oracle-query count for k > 1, the section seeks the oracle-evaluation complexity at which that advantage holds within the time window.Source: Determining maximum operation counts… · p. 6
Determining I/O bandwidth
The section estimates quantum I/O bandwidth by assuming one quantum gate per bit and using all 10,000 qubits for reading and writing, while taking classical-chip bandwidth from NVIDIA’s A100 datasheet.
- Using all 10,000 qubits for I/O and assuming one gate per bit gives an estimated quantum bandwidth of B≈10,000; classical-chip bandwidth comes from NVIDIA’s A100 datasheet.Source: Determining I/O bandwidth · p. 6