Exploiting the coherence and entanglement of quantum many-qubit states, quantum computing can significantly surpass classical algorithms, making it possible to factor large numbers, solve linear equations, simulate many-body quantum systems, etc., in a reasonable time. With the rapid development of quantum computing hardware, many attention has been drawn to explore how quantum computers could go beyond the limit of classical computation. Owing to the need of a universal fault-tolerant quantum computer for many existing quantum algorithms, such as Shor’s factoring algorithm, and considering the limit of near-term quantum devices with small qubit numbers and short coherence times, many recent works focused on the exploration of demonstrating quantum advantages using noisy intermediate-scaled quantum devices and shallow circuits, and hence some sampling problems have been proposed as the candidates for quantum advantage demonstration. This review summarizes quantum advantage problems that are realizable on current quantum hardware. We focus on two notable problems—random circuit simulation and boson sampling—and consider recent theoretical and experimental progresses. After the respective demonstrations of these two types of quantum advantages on superconducting and optical quantum platforms, we expect current and near-term quantum devices could be employed for demonstrating quantum advantages in general problems.
Exploiting the coherence and entanglement of quantum many-qubit states, quantum computing can significantly surpass classical algorithms, making it possible to factor large numbers, solve linear equations, simulate many-body quantum systems, etc., in a reasonable time. With the rapid development of quantum computing hardware, many attention has been drawn to explore how quantum computers could go beyond the limit of classical computation. Owing to the need of a universal fault-tolerant quantum computer for many existing quantum algorithms, such as Shor’s factoring algorithm, and considering the limit of near-term quantum devices with small qubit numbers and short coherence times, many recent works focused on the exploration of demonstrating quantum advantages using noisy intermediate-scaled quantum devices and shallow circuits, and hence some sampling problems have been proposed as the candidates for quantum advantage demonstration. This review summarizes quantum advantage problems that are realizable on current quantum hardware. We focus on two notable problems—random circuit simulation and boson sampling—and consider recent theoretical and experimental progresses. After the respective demonstrations of these two types of quantum advantages on superconducting and optical quantum platforms, we expect current and near-term quantum devices could be employed for demonstrating quantum advantages in general problems.
Abstract The achievement of quantum computational advantage, also known as quantum supremacy, is a major milestone at which a quantum computer can solve a problem significantly faster than the world's most powerful classical computers. Two tasks, boson sampling and random quantum circuit sampling, have experimentally exhibited quantum advantages on photonic and superconducting platforms respectively. Classical benchmarking is essential, yet challenging, because these tasks are intractable for classical computers. This study reviews models, algorithms and large‐scale simulations of these two sampling tasks. These approaches continue to hold substantial significance for research in both current noisy intermediate‐scale quantum (NISQ) systems and future fault‐tolerant quantum computing.
The current stage of quantum computing development is defined by Noisy Intermediate-Scale Quantum (NISQ) devices, which operate with a moderate number of qubits that are inherently susceptible to noise and decoherence. Despite the absence of full error correction, NISQ systems have demonstrated the ability to perform computational tasks that challenge classical simulation under certain conditions. This paper explores the concept of quantum advantage in the NISQ era by analysing prominent algorithmic approaches, benchmarking methodologies, and the practical constraints imposed by contemporary hardware. Hybrid quantum–classical algorithms, sampling-based experiments, and performance metrics are examined to assess the extent to which near-term quantum devices can outperform classical systems. The study finds that while progress toward quantum advantage is evident, significant technical and algorithmic limitations prevent its widespread realization. The paper concludes by identifying key research directions required to bridge the gap between experimental demonstrations and practical quantum computing applications.
Quantum computing has transitioned from a theoretical curiosity to an emerging technological paradigm with demonstrable computational advantages in specific problem domains. This paper presents a comprehensive review of current advances in quantum computing hardware, software, and near-term applications within the Noisy Intermediate-Scale Quantum (NISQ) era. We examine the architectural evolution of leading quantum platforms, including superconducting, trapped-ion, and photonic systems, analyzing their qubit counts, gate fidelities, and coherence times. The paper evaluates key quantum algorithms Shor's factoring algorithm [1], Grover's search algorithm [2], the Variational Quantum Eigensolver (VQE) [3], and the Quantum Approximate Optimization Algorithm (QAOA) [4] in the context of their practical applicability to real-world problems. We further discuss the milestone of quantum computational advantage demonstrated by Google's Sycamore processor [5] and IBM's ambitious hardware roadmap toward fault-tolerant quantum computing [6]. Our analysis reveals that while universal fault-tolerant quantum computing remains a long-term objective, NISQ-era devices are already yielding valuable results in quantum chemistry simulation, combinatorial optimization, and quantum machine learning. We conclude by identifying the critical challenges—error correction, scalability, and algorithm design that must be addressed to realize the full potential of quantum computing.
Quantum mechanics promises computational powers beyond the reach of classical computers. Current technology is on the brink of an experimental demonstration of the superior power of quantum computation compared to classical devices. For such a demonstration to be meaningful, experimental noise must not affect the computational power of the device; this occurs when a classical algorithm can use the noise to simulate the quantum system. In this work, we demonstrate an algorithm which simulates boson sampling, a quantum advantage demonstration based on many-body quantum interference of indistinguishable bosons, in the presence of optical loss. Finding the level of noise where this approximation becomes efficient lets us map out the maximum level of imperfections at which it is still possible to demonstrate a quantum advantage. We show that current photonic technology falls short of this benchmark. These results call into question the suitability of boson sampling as a quantum advantage demonstration.
Quantum computation exploits superposition, entanglement, interference, and measurement to process information.Research has moved from theoretical algorithms to functional devices where the performance is not only limited by qubit physics, but also by the control, compilation, error mitigation, and error correction.This review considers quantum computing on various levels of abstraction, including physical qubits, quantum algorithms, system architecture, fault-tolerance, and emerging applications.Study-specific evidence regarding scale, operational quality, connectivity, control and suppression of errors is compared across the different types of superconducting circuits, trapped ions, semiconductor spin qubits, neutral atoms and photonic processors.The review of the fundamental algorithms, noisy intermediate-scale quantum computing, variational and hybrid quantum-classical approaches, quantum simulation, quantum machine learning, and security implications is also discussed.Measurable progress has been demonstrated in published experiments for logical-qubit operation, below-threshold surface-code memory, programmable photonic sampling and platformspecific scaling.However, the reported metrics are not directly interchangeable, and practical advantage remains task-and baseline-dependent.Further progress will need to be accompanied by coordinated developments in hardware reliability, error correction, classical control, estimates of algorithmic resources, and clear classical method comparisons.
Boson Sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quantum devices. However, noise in experimental implementations poses a significant challenge, potentially rendering Boson Sampling classically simulable and compromising its classical intractability. Numerous studies have proposed classical algorithms that can efficiently simulate Boson Sampling under various noise models, particularly as noise rates increase with circuit depth. To address this challenge, we investigate the viability of achieving quantum computational advantage through Boson Sampling implemented with shallow-depth linear optical circuits. In particular, as the average-case hardness of estimating output probabilities of Boson Sampling is a crucial ingredient in demonstrating its classical intractability, we make progress on establishing the average-case hardness of Boson Sampling confined to logarithmic-depth regimes. We also obtain the average-case hardness for logarithmic-depth Fock-state Boson Sampling subject to lossy environments and for the logarithmic-depth Gaussian Boson Sampling. By providing complexity-theoretical backgrounds for the classical simulation hardness of logarithmic-depth Boson Sampling, we expect that our findings will mark a crucial step towards a more noise-tolerant demonstration of quantum advantage with shallow-depth Boson Sampling.