Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Exploring shallow-depth boson sampling: Toward a scalable quantum advantage

Byeongseon Go, Changhun Oh, Liang Jiang, Hyunseok Jeong

Published May 7, 2024• 9 citations
Publisher

Abstract

Boson sampling is a promising candidate for showcasing quantum advantage. However, achieving this advantage involves pinpointing the optimal balance between shallow-depth circuits, which are susceptible to classical simulation, and larger-depth circuits prone to noise. Here, the authors introduce a linear-optical circuit design with nonlocal gates, aimed at enhancing the probability of demonstrating advantage even with shallow circuit depths.

DOI
10.1103/physreva.109.052613

Related papers

Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy

Byeongseon Go, Changhun Oh, Liang Jiang +1 more

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.

arXiv:2306.10671•Jun 19, 2023•0 citations

Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions

Haoyu Qi, Diego Cifuentes, Kamil Brádler +3 more

Gaussian boson sampling is a candidate model for demonstrating quantum computational advantage in photonic systems. Here, the authors narrow down the range of possible architectures for such a demonstration, by introducing a classical algorithm that can simulate optical systems with shallow-depth circuits and local gates in polynomial time.

Physical Review A•May 6, 2022•12 citations

On computational complexity and average-case hardness of shallow-depth boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

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.

arXiv:2405.01786•Quantum•Mar 13, 2026•1 citation

Review on quantum advantages of sampling problems

Ying Li, Ze-Yao Han, Chao-Jian Li +3 more

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.

Acta Physica Sinica•Jan 1, 2021•2 citations

Logarithmic-depth quantum simulation of boson sampling

Changhun Oh

We show that boson sampling with an arbitrary $m$-mode interferometer and $n\le m$ single-photon inputs can be simulated to inverse-polynomial total-variation error by a logarithmic-depth qubit circuit with polynomially many qubits. The circuit uses Clifford+$T$ gates, arbitrary qubit connectivity, and a single final measurement, and its family is logspace uniform. The key idea is to enlarge the optical system, decompose the resulting transformation into six quadratic shears, and distribute each mode over many submodes. This redistribution permits a fixed local occupation cutoff, after which local basis changes and parallel phase gates give the qubit circuit. Consequently, our result places boson sampling within shallow quantum computation.

quant-pharXiv:2609.18907•Sep 17, 2026•0 citations

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

quant-pharXiv:2609.01448•Sep 2, 2026•0 citations
Boson sampling is a promising candidate for showcasing quantum advantage. However, achieving this advantage involves pinpointing the optimal balance between shallow-depth circuits, which are susceptible to classical simulation, and larger-depth circuits prone to noise. Here, the authors introduce a linear-optical circuit design with nonlocal gates, aimed at enhancing the probability of demonstrating advantage even with shallow circuit depths.
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.
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.
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.
We show that boson sampling with an arbitrary mmm-mode interferometer and n≤mn\le mn≤m single-photon inputs can be simulated to inverse-polynomial total-variation error by a logarithmic-depth qubit circuit with polynomially many qubits. The circuit uses Clifford+TTT gates, arbitrary qubit connectivity, and a single final measurement, and its family is logspace uniform. The key idea is to enlarge the optical system, decompose the resulting transformation into six quadratic shears, and distribute each mode over many submodes. This redistribution permits a fixed local occupation cutoff, after which local basis changes and parallel phase gates give the qubit circuit. Consequently, our result places boson sampling within shallow quantum computation.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[log⁡log⁡]\mathsf{QNC}^0[\log\log]QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0\mathsf{QAC}^0QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.