Abstract: On the basis of its unrivalled potential to solve factorization problems and further application in cryptography, quantum computing is considered as one of the most promising computational models for the future. It provides a new angle for thinking of computation and a new approach for attack various computationally difficult problems. In this article, we give a comprehensive survey of developments in the last twenty years on quantum algorithms, quantum complexity, quantum programming theory, quantum circuits, and quantum cryptography that we hope will serve as references for researchers in related fields. We also outline various research directions and open problems in this area, with the hope of prompting further progress or even solutions.
Introduction
While the theoretical potential of quantum computing—exemplified by Shor’s algorithm for factoring large integers—has been known for decades, the field has historically been fragmented. Researchers often specialize in narrow silos like hardware-level circuit optimization, high-level programming language design, or abstract complexity theory. This survey seeks to bridge the gap between these sub-fields, providing a roadmap for how we move from mathematical curiosities to practical, programmable, and verifiable quantum advantage.
Quantum Complexity Theory
A fundamental goal of quantum computing research is to identify the "quantum supremacy" boundary: exactly where and why do quantum computers beat classical ones? This is explored through the lens of complexity classes.
Key classes include P (polynomial time), BPP (bounded-error probabilistic polynomial time), and BQP (bounded-error quantum polynomial time). One of the most striking insights in the field is the use of "oracles" (black-box functions) to prove separations between quantum and classical power. While we don't yet know if $P = BQP$ in the real world, we can prove they are different in "relativized" worlds where certain functions are given for free.
As shown in the figure above, the relationship between BQP and NP remains one of the greatest mysteries in computer science. We know that BQP is contained within PSPACE, and landmark proofs have shown that QIP (Quantum Interactive Proof systems) is exactly equal to PSPACE. However, whether BQP contains NP—or vice versa—remains an open question.
Algorithmic Frameworks and Query Complexity
Beyond the famous Shor and Grover algorithms, several meta-algorithms have emerged as powerful design frameworks:
- Quantum Walks: Much like Markov Chain Monte Carlo (MCMC) in classical computing, Quantum Walks provide a generalized way to achieve polynomial speedups for a massive variety of search and sampling problems.
- The HHL Algorithm: This algorithm offers an exponential speedup for solving linear equations ($Ax=b$). However, it faces the "Input Problem"—the significant difficulty of efficiently loading classical data into a quantum state.
- Query Complexity: There is a significant gap between classical and quantum query complexity for Boolean functions. For certain functions, quantum computers require significantly fewer "looks" at the data than any possible classical algorithm.
Programming Theory and Circuit Synthesis
As we move toward practical implementation, the "Quantum Data, Classical Control" paradigm has become dominant. Most successful quantum programming languages (e.g., Quipper, QFC) adopt a hybrid approach where the heavy lifting of state manipulation happens on quantum hardware, while the logic flow and error handling remain classical.
In terms of hardware realization, circuit synthesis focuses on reducing the cost of the Toffoli gate, a universal gate for reversible computing. Efficiently synthesizing these gates is a critical building block for practical, fault-tolerant quantum architectures.
Quantum Cryptography and Verification
Quantum cryptography has evolved beyond basic key distribution (QKD) to device-independent protocols. These protocols are designed to be secure even if the hardware manufacturer is untrusted.
Furthermore, as quantum computers become more powerful, we face a verification paradox: if a quantum computer solves a problem a classical computer cannot, how do we verify the answer? Boson Sampling has emerged as a key experimental battleground for testing this verification of quantum supremacy.
Limitations and Future Frontiers
Despite two decades of rapid progress, several bottlenecks remain:
- The QRAM Bottleneck: Many promising algorithms rely on "Quantum RAM" to function efficiently, yet building a physical QRAM remains a daunting hardware challenge.
- The NISQ Era: Most theoretical progress assumes "perfect" qubits. Bridging the gap to the NISQ (Noisy Intermediate-Scale Quantum) era—where qubits are few and noisy—is the next major frontier.
- Fault Tolerance: Current device-independent cryptographic protocols require extremely high detection efficiencies that are difficult to achieve in current laboratory settings.
Solving these problems will require continued interdisciplinary collaboration across complexity theory, algorithm design, and experimental physics.
Summary updated