The Learning Stabilizers with Noise problem

• URL: http://arxiv.org/abs/2410.18953v5
• Date: Mon, 14 Apr 2025 22:20:52 GMT
• Title: The Learning Stabilizers with Noise problem
• Authors: Alexander Poremba, Yihui Quek, Peter Shor,
• Abstract summary: We show that the Learning Parity with Noise (LPN) problem can be seen as the task of decoding a random linear code in the presence of noise.<n>We show that LSN includes as a special case, which suggests that it is at least as hard as its classical counterpart.<n>We identify several applications of our LSN assumption, ranging from the construction of quantum bit schemes to the computational limitations of learning from quantum data.
• Score: 46.623273455512106
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) problem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. We give both polynomial-time and exponential-time quantum algorithms for solving LSN in various depolarizing noise regimes, ranging from extremely low noise, to low constant noise rates, and even higher noise rates up to a threshold. Next, we provide concrete evidence that LSN is hard. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical counterpart. Second, we prove a worst-case to average-case reduction for variants of LSN. We then ask: what is the computational complexity of solving LSN? Because the task features quantum inputs, its complexity cannot be characterized by traditional complexity classes. Instead, we show that the LSN problem lies in a recently introduced (distributional and oracle) unitary synthesis class. Finally, we identify several applications of our LSN assumption, ranging from the construction of quantum bit commitment schemes to the computational limitations of learning from quantum data.

Related papers

• Classical Verification of Quantum Learning Advantages with Noises [0.27930367518472443]
  We propose an efficient classical error rectification algorithm to reconstruct the noise-free results given by the quantum Fourier sampling circuit. We also prove that a classical client with access to the random example oracle can verify the agnostic parity learning results from the noisy quantum prover.
  arXiv  Detail & Related papers  (2024-11-14T06:14:39Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. This paper attempts to find a reduction from the decoding problem of linear codes, for which several hardness results exist. We characterize the efficiency of the reduction in terms of the parameters of the decoding and problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
  We provide a-time classical algorithm for noisy quantum circuits. Our approach is based upon the intuition that noise exponentially damps non-local correlations. For constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
  arXiv  Detail & Related papers  (2024-07-17T17:48:39Z)
• Comparing resource requirements of noisy quantum simulation algorithms for the Tavis-Cummings model [0.0]
  Fault-tolerant quantum computers could facilitate the simulation of quantum systems unfeasible for classical computation. These include quantum error mitigation (QEM) for alleviating device noise, and variational quantum algorithms (VQAs) which combine classical optimization with short-depth, parameterized quantum circuits. We compare two such methods: zero-noise extrapolation (ZNE) with noise amplification by circuit folding, and incremental structural learning (ISL) We find that while ISL achieves lower error than ZNE for smaller system sizes, it fails to produce correct dynamics for 4 qubits, where ZNE is superior.
  arXiv  Detail & Related papers  (2024-02-26T16:06:24Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• On the Hardness of PAC-learning stabilizer States with Noise [5.584060970507507]
  We consider the problem of learning stabilizer states with noise in the Probably Approximately Correct (PAC) framework of Aaronson (2007) for learning quantum states. Motivated by approaches to noise tolerance from classical learning theory, we introduce the Statistical Query (SQ) model for PAC-learning quantum states. We prove that algorithms in this model are indeed resilient to common forms of noise, including classification and depolarizing noise.
  arXiv  Detail & Related papers  (2021-02-09T23:06:54Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms [0.3562485774739681]
  Variational Quantum Algorithms (VQAs) may be a path to quantum advantage on Noisy Intermediate-Scale Quantum (NISQ) computers. We rigorously prove a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau.
  arXiv  Detail & Related papers  (2020-07-28T17:52:21Z)

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.