Noise and the frontier of quantum supremacy

• URL: http://arxiv.org/abs/2102.01738v2
• Date: Wed, 9 Jun 2021 23:00:41 GMT
• Title: Noise and the frontier of quantum supremacy
• Authors: Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu
• Abstract summary: Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. We study the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction.
• Score: 1.3375143521862154
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity in these highly noisy devices. Surprisingly, we show that it remains hard to compute the output probabilities of noisy random quantum circuits without error correction. More formally, so long as the noise rate of the device is below the error detection threshold, we show it is #P-hard to compute the output probabilities of random circuits with a constant rate of noise per gate. This hardness persists even though these probabilities are exponentially close to uniform. Interestingly these hardness results also have implications for the complexity of experiments in a low-noise setting. The issue here is that prior hardness results for computing output probabilities of random circuits are not robust enough to imprecision to connect with the Stockmeyer argument for hardness of sampling from circuits with constant fidelity. We exponentially improve the robustness of prior results to imprecision, both in the cases of Random Circuit Sampling and BosonSampling. In the latter case we bring the proven hardness within a constant factor in the exponent of the robustness required for hardness of sampling for the first time. We then show that our results are in tension with one another -- the high-noise result implies the low-noise result is essentially optimal, even with generalizations of our techniques.

Related papers

• 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)
• Provable bounds for noise-free expectation values computed from noisy samples [1.3194391758295114]
  We quantify the sampling overhead to extract good samples from noisy quantum computers. We show how this allows us to use the Conditional Value at Risk of noisy samples to determine provable bounds on noise-free expectation values.
  arXiv  Detail & Related papers  (2023-12-01T17:12:18Z)
• 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)
• 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)
• Quantum emulation of the transient dynamics in the multistate Landau-Zener model [50.591267188664666]
  We study the transient dynamics in the multistate Landau-Zener model as a function of the Landau-Zener velocity. Our experiments pave the way for more complex simulations with qubits coupled to an engineered bosonic mode spectrum.
  arXiv  Detail & Related papers  (2022-11-26T15:04:11Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• 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)
• Benchmarking near-term quantum computers via random circuit sampling [3.48887080077816]
  We develop an algorithm that can sample-efficiently estimate the total amount of noise induced by a layer of arbitrary non-Clifford gates. Our algorithm is inspired by Google's quantum supremacy experiment and is based on random circuit sampling.
  arXiv  Detail & Related papers  (2021-05-11T17:49:16Z)
• 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)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

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.