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

• URL: http://arxiv.org/abs/2405.01786v1
• Date: Fri, 3 May 2024 00:12:48 GMT
• Title: On computational complexity and average-case hardness of shallow-depth boson sampling
• Authors: Byeongseon Go, Changhun Oh, Hyunseok Jeong,
• Abstract summary: Boson sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage. Noise in experimental implementations poses a significant challenge, potentially rendering boson sampling classically simulable and compromising its classical intractability. We explore the viability of achieving quantum computational advantage through boson sampling with shallow-depth linear optical circuits.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 under various noise models that can efficiently simulate boson sampling as noise rates increase with circuit depth. To address this issue particularly related to circuit depth, we explore the viability of achieving quantum computational advantage through boson sampling with shallow-depth linear optical circuits. Specifically, 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 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.

Related papers

• Variational Tensor Network Simulation of Gaussian Boson Sampling and Beyond [0.0]
  We propose a classical simulation tool for general continuous variable sampling problems. We reformulate the sampling problem as that of finding the ground state of a simple few-body Hamiltonian. We validate our method by simulating Gaussian Boson Sampling, where we achieve results comparable to the state of the art.
  arXiv  Detail & Related papers  (2024-10-24T13:43:06Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Demonstration of Robust and Efficient Quantum Property Learning with Shallow Shadows [1.412425180760368]
  We propose a robust shallow shadows protocol for characterizing quantum states on current quantum computing platforms. Our protocol correctly recovers state properties such as expectation values, fidelity, and entanglement entropy, while maintaining a lower sample complexity. This combined theoretical and experimental analysis positions the robust shallow shadow protocol as a scalable, robust, and sample-efficient protocol.
  arXiv  Detail & Related papers  (2024-02-27T21:53:32Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy [1.7635061227370266]
  Boson sampling is a sampling task proven to be hard to simulate efficiently using classical computers. We propose a shallow-depth linear optical circuit architecture that can overcome the problems associated with geometrically local architectures.
  arXiv  Detail & Related papers  (2023-06-19T02:11:54Z)
• Classical algorithm for simulating experimental Gaussian boson sampling [2.1684911254068906]
  Gaussian boson sampling is a promising candidate for showing experimental quantum advantage. Despite a high photon loss rate and the presence of noise, they are currently claimed to be hard to classically simulate with the best-known classical algorithm. We present a classical tensor-network algorithm that simulates Gaussian boson sampling and whose complexity can be significantly reduced when the photon loss rate is high.
  arXiv  Detail & Related papers  (2023-06-06T14:19:48Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Noise thresholds for classical simulability of non-linear Boson sampling [4.812718493682455]
  We introduce higher order non-linearities as a mean to enhance the computational complexity of the problem and the protocol's robustness against noise. Our results indicate that the addition of single-mode Kerr non-linearity at the input state preparation level, while retaining a linear-optical evolution, makes the Boson sampling protocol more robust against noise.
  arXiv  Detail & Related papers  (2022-02-24T12:17:28Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.