Quantum computing has progressed from theoretical speculation to experimental realization, leading to milestone demonstrations that claim computational superiority over classical systems. Among these milestones, quantum supremacy experiments have attracted considerable attention by showcasing tasks that are infeasible for classical computation within reasonable time limits. However, the practical value of such demonstrations remains a subject of debate. This paper critically evaluates the distinction between quantum supremacy and quantum utility, emphasizing their conceptual differences, experimental foundations, and real-world relevance. By examining key experimental results, algorithmic developments, and benchmarking approaches, the study argues that quantum utility-defined by practical, application-oriented performance-provides a more meaningful metric for long-term progress. The paper highlights the limitations of supremacy-based demonstrations and discusses pathways toward achieving utility-driven quantum advantage in the near and long term.
Quantum computing has progressed from theoretical speculation to experimental realization, leading to milestone demonstrations that claim computational superiority over classical systems. Among these milestones, quantum supremacy experiments have attracted considerable attention by showcasing tasks that are infeasible for classical computation within reasonable time limits. However, the practical value of such demonstrations remains a subject of debate. This paper critically evaluates the distinction between quantum supremacy and quantum utility, emphasizing their conceptual differences, experimental foundations, and real-world relevance. By examining key experimental results, algorithmic developments, and benchmarking approaches, the study argues that quantum utility-defined by practical, application-oriented performance-provides a more meaningful metric for long-term progress. The paper highlights the limitations of supremacy-based demonstrations and discusses pathways toward achieving utility-driven quantum advantage in the near and long term.
Quantum computing has recently achieved experimental demonstrations of quantum advantage, marking a major milestone toward beyond-classical computation. However, translating these demonstrations into practical utility remains a central challenge. In this perspective, we argue that this transition is fundamentally limited by three interconnected gaps: the utility gap between benchmark tasks and real-world applications, the algorithmic gap between asymptotic quantum speedups and realistic performance, and the hardware gap imposed by noisy intermediate-scale devices. We further highlight that recent progress is beginning to narrow these gaps through the rapid maturation of quantum hardware, the emergence of resource-aware and practically grounded quantum algorithms, and the increasing integration of classical computation into the quantum workflow. Finally, we discuss potential early application domains for practical quantum advantage, while emphasizing that its ultimate realization will likely emerge from the co-evolution of hardware, algorithms, and application-driven discovery rather than any single breakthrough.
This thesis examines the theoretical foundations that enable near-term quantum computational utility. Quantum utility occurs when a quantum computer contributes meaningfully to solving a computational task that a classical computer cannot alone replicate without additional time or loss of accuracy. Unlike quantum advantage, which requires provable superiority over all classical methods, quantum utility requires only practical usefulness, employing quantum devices as effective tools for scientific discovery. Recognising this distinction is essential for directing research towards pragmatic goals achievable with current and emerging hardware. The thesis comprises a three-part investigation encompassing theoretical limits, algorithmic design, and hybrid applications. First, it characterises the boundary between classically simulable and intrinsically quantum computations by analysing a specific class of simulable circuits. Second, it designs and analyses specialised quantum algorithms for structured problems using the framework of parameterized complexity. Finally, it demonstrates pragmatic algorithm design through a hybrid classical–quantum approach to a key problem in computational genomics, illustrating how theoretical progress can translate into tangible near-term utility.
Quantum supremacy refers to the experimental demonstration that a quantum computing device performs a calculation that no classical computer can match in a reasonable time. Such machines would not be useful for solving problems of practical interest, but they would provide a proof of principle that larger and more useful machines could be built. The gap between classical and quantum computing is potentially enormous, and the apparent ease with which quantum states can be prepared, manipulated, and measured has led many to believe that quantum devices might one day outperform classical hardware at solving a broad range of computational tasks. The most immediate goal of progress in quantum engineering is the construction of a device that passes the proofs of principle of quantum supremacy experiments. They would transform a state that can be initialized neutrally, evolve it under a controlled Hamiltonian, then sample from the output distribution. Such devices must possess sufficient connectivity and low noise but can be cared for by classical software. Their demonstration would mark a historic milestone in the development of quantum technology, providing intrigue and awe but little societal benefit. However, if they can be produced with sufficient fidelity and scale, there is hope that more generally applicable quantum engines might be constructed that could exploit the exponential speedup to outperform classical computers for problems of deep societal importance.
Quantum computing, leveraging the principles of superposition and entanglement, has emerged as a revolutionary technology with the potential to outperform classical computers in specific tasks. This paper explores the concept of quantum supremacy, marked by Google's Sycamore processor, and its implications for classical computing. It discusses the foundations of quantum computing, including qubits, superposition, and key quantum algorithms like Shor's and Grover's, highlighting their advantages over classical systems. This study addresses the milestones in achieving quantum supremacy, including experimental benchmarks and performance comparisons. The challenges in scaling quantum systems, mitigating decoherence, and addressing criticisms of quantum supremacy claims are examined. Additionally, the paper outlines emerging applications in cryptography, optimization, and artificial intelligence and emphasizes the importance of hybrid quantum-classical systems in bridging current technological gaps. The future of quantum computing lies in advancing fault-tolerant systems and fostering interdisciplinary collaborations to realize its transformative potential across industries.
Abstract Quantum computing leverages fundamental quantum-mechanical phenomena—most notably superposition, entanglement, and quantum tunneling—to perform computations in ways that differ fundamentally from classical digital processing. Compared to conventional computing architectures, quantum systems promise significant reductions in computational time and potentially lower energy consumption for specific classes of problems. These advantages, combined with advances in nanoscale engineering and the slowing of traditional hardware scaling trends such as Moore’s Law, have led to substantial commercial and national-security-driven investments in quantum technologies over the past decade. A major milestone was reached when Google announced the experimental demonstration of “quantum supremacy,” showing that a quantum processor could execute a specific computational task infeasible for a classical supercomputer within practical time constraints. Although the demonstrated problem had no immediate practical application, this achievement marked a crucial step toward the development of quantum systems capable of delivering real-world computational advantages and provided a more precise technical framing of the concept of quantum advantage. Despite the fact that the mathematical foundations, programming models, and principal quantum algorithms were established in the 1990s, quantum computing remained largely confined to a specialized research community for decades. Today, the increasing accessibility of cloud-based quantum hardware calls for a broader dissemination of implementation-oriented knowledge among researchers and practitioners in computer science, software engineering, and related fields. The quantum programming paradigm differs fundamentally from classical programming models and often relies on physical and algebraic notations that may pose barriers to traditionally trained computer scientists. This series of articles provides a self-contained and concise introduction to quantum computing and its core algorithms, with a strong emphasis on practical implementation. Given that real quantum processors—such as those accessible via the IBM quantum ecosystem—are now available as cloud services, experimental validation can be conducted both on simulators and on actual hardware for small-scale inputs. While other platforms such as Rigetti and IonQ also offer cloud-based quantum computing services, this review focuses exclusively on the IBM quantum computing ecosystem.
In quantum computing, a demonstration of quantum supremacy (or quantum advantage) consists of presenting a task, possibly of no practical value, whose computation is feasible on a quantum device, but cannot be performed by classical computers in any feasible amount of time. The notable claim of quantum supremacy presented by Google’s team in 2019 consists of demonstrating the ability of a quantum circuit to generate, albeit with considerable noise, bitstrings from a distribution that is considered hard to simulate on classical computers. Very recently, in 2020, a quantum supremacy claim was presented by a group from the University of Science and Technology of China, using a different technology and generating a different distribution, but sharing some statistical principles with Google’s demonstration. Verifying that the generated data is indeed from the claimed distribution and assessing the circuit’s noise level and its fidelity is a statistical undertaking. The objective of this paper is to explain the relations between quantum computing and some of the statistical aspects involved in demonstrating quantum supremacy in terms that are accessible to statisticians, computer scientists, and mathematicians. Starting with the statistical modeling and analysis in Google’s demonstration, which we explain, we study various estimators of the fidelity, and different approaches to testing the distributions generated by the quantum computer. We propose different noise models, and discuss their implications. A preliminary study of the Google data, focusing mostly on circuits of 12 and 14 qubits is given in different parts of the paper.