Abstract Transmon qubits have traditionally been regarded as limited to random circuit sampling, incapable of performing Fock state boson sampling—a problem known to be classically intractable. This work challenges that assumption by introducing q -boson Fock state sampling, a variant in which transmon qubits can operate effectively. Through direct mapping to the q -boson formalism, we demonstrate that transmons possess the capability to achieve quantum supremacy in q -boson sampling tasks. This finding expands the potential applications of transmon-based quantum processors and paves the way for new avenues in quantum computation.
Abstract Transmon qubits have traditionally been regarded as limited to random circuit sampling, incapable of performing Fock state boson sampling—a problem known to be classically intractable. This work challenges that assumption by introducing q -boson Fock state sampling, a variant in which transmon qubits can operate effectively. Through direct mapping to the q -boson formalism, we demonstrate that transmons possess the capability to achieve quantum supremacy in q -boson sampling tasks. This finding expands the potential applications of transmon-based quantum processors and paves the way for new avenues in quantum computation.
Boson sampling is a sampling task proven to be hard to simulate efficiently using classical computers under plausible assumptions, which makes it an appealing candidate for quantum supremacy. However, due to a large noise rate for near-term quantum devices, it is still unclear whether those noisy devices maintain the quantum advantage for much larger quantum systems. Since the noise rate typically grows with the circuit depth, an alternative is to find evidence of simulation hardness at the shallow-depth quantum circuit. To find the evidence, one way is to identify the minimum depth required for the average-case hardness of approximating output probabilities, which is considered a necessary condition for the state-of-the-art technique to prove the simulation hardness of boson sampling. In this work, we analyze the output probability distribution of shallow-depth boson sampling for Fock-states and Gaussian states, and examine the limitation of the average-case hardness argument at this shallow-depth regime for geometrically local architectures. We propose a shallow-depth linear optical circuit architecture that can overcome the problems associated with geometrically local architectures. Our numerical results suggest that this architecture demonstrates possibilities of average-case hardness properties in a shallow-depth regime, through its resemblance to the global Haar-random boson sampling circuit. This result implies that the corresponding architecture has the potential to be utilized for scalable quantum supremacy with its shallow-depth boson sampling.
Abstract Since the dawn of quantum computation science, a range of quantum algorithms have been proposed, yet few have experimentally demonstrated a definitive quantum advantage. Shor’s algorithm, while renowned, has not been realized at a scale to outperform classical methods. In contrast, Fock-state boson sampling has been theoretically established, under standard complexity-theoretic assumptions, as a promising route toward quantum computational advantage. However, most existing experimental realizations of boson sampling to date have been based on Gaussian boson sampling, in which the input states consist of squeezed states of light. In this work, we introduce a higher-spin ( S ) sampling framework and show that it provides a practical path toward quantum computational advantage. We derive a quasi-linear scaling relation between the number of sites m and the number of spins n , namely m ~ n 1+ ϵ , where ϵ = 3/(2 S ) decreases with increasing spin quantum number. This suggests that, within a spin system, Fock-state boson sampling can be implemented in a quasi-linear mode regime ( m = Ω ( n 1+ ϵ )), significantly reducing experimental resource requirements.
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.
This study aims to analyze recent developments in quantum supremacy by comparing the computational performance of stabilized superconducting qubit systems with classical supercomputing capabilities. A systematic literature review was conducted on major experimental studies published between 2019 and 2024, focusing on random circuit sampling, qubit stability, gate fidelity, and computational runtime comparisons. The analysis covers key quantum processors, including Sycamore and Zuchongzhi, by evaluating three main parameters: number of qubits, circuit complexity, and performance gap relative to classical simulation.The results show that quantum processors with 50–100 qubits and high gate fidelity are able to complete specific sampling tasks within seconds to hours, whereas equivalent classical simulations would require thousands to billions of years. The findings also indicate that computational advantage increases exponentially with system scale and is strongly influenced by qubit stability and error suppression techniques. Although the demonstrated tasks remain specialized and not yet applicable to practical problems, the evidence confirms that stabilized qubit systems have achieved a measurable computational regime beyond classical feasibility.This review provides a clear synthesis of current experimental achievements and highlights that future progress toward practical quantum advantage depends on improvements in error correction, scalability, and hardware reliability.
Boson sampling represents a promising approach to obtain evidence of the supremacy of quantum systems as a resource for the solution of computational problems. The classical hardness of Boson Sampling has been related to the so called Permanent-of-Gaussians Conjecture and has been extended to some generalizations such as Scattershot Boson Sampling, approximate and lossy sampling under some reasonable constraints. However, it is still unclear how demanding these techniques are for a quantum experimental sampler. Starting from a state of the art analysis and taking account of the foreseeable practical limitations, we evaluate and discuss the bound for quantum supremacy for different recently proposed approaches, accordingly to today's best known classical simulators.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 50 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.