Quantum Advantage with Faulty Oracle

• URL: http://arxiv.org/abs/2411.04931v1
• Date: Thu, 07 Nov 2024 18:10:07 GMT
• Title: Quantum Advantage with Faulty Oracle
• Authors: David Rasmussen Lolck, Laura Mančinska, Manaswi Paraashar,
• Abstract summary: We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise. Regev and Schiff (ICALP'08) showed that quantum advantage is lost for the search problem under this noise model. This is the first non-trivial robustification of quantum query algorithms against an oracle that is noisy.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper investigates the impact of noise in the quantum query model, a fundamental framework for quantum algorithms. We focus on the scenario where the oracle is subject to non-unitary (or irreversible) noise, specifically under the \textit{faulty oracle} model, where the oracle fails with a constant probability and acts as identity. Regev and Schiff (ICALP'08) showed that quantum advantage is lost for the search problem under this noise model. Our main result shows that every quantum query algorithm can be made robust in this noise model with a roughly quadratic blow-up in query complexity, thereby preserving quantum speedup for all problems where the quantum advantage is super-cubic. This is the first non-trivial robustification of quantum query algorithms against an oracle that is noisy.

Related papers

• Noisy Quantum Learning Theory [2.956729394666618]
  We develop a framework for learning from noisy quantum experiments.<n>We focus on fault-tolerant devices accessing uncharacterized systems through noisy couplings.
  arXiv  Detail & Related papers  (2025-12-11T18:56:32Z)
• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  This thesis is centered around simulating quantum dynamics on quantum devices.<n>We present an overview of the most relevant quantum algorithms for quantum dynamics.<n>We identify relevant problems within quantum dynamics that could benefit from quantum simulation in the near future.
  arXiv  Detail & Related papers  (2025-08-29T10:37:19Z)
• Power Characterization of Noisy Quantum Kernels [52.47151453259434]
  We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small. We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
  arXiv  Detail & Related papers  (2024-01-31T01:02:16Z)
• Limitations of Noisy Quantum Devices in Computational and Entangling Power [5.178527492542246]
  We show that noisy quantum devices with a circuit depth of more than $O(log n)$ provide no advantages in any quantum algorithms. We also study the maximal entanglement that noisy quantum devices can produce under one- and two-dimensional qubit connections.
  arXiv  Detail & Related papers  (2023-06-05T12:29:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Complexity analysis of weakly noisy quantum states via quantum machine learning [1.203955415344484]
  We focus on the complexity of weakly noisy states, which we define as the size of the shortest quantum circuit required to prepare the noisy state. We propose a quantum machine learning (QML) algorithm that exploits the intrinsic-connection property of structured quantum neural networks.
  arXiv  Detail & Related papers  (2023-03-31T06:02:44Z)
• 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)
• A quantum algorithm for solving open system dynamics on quantum computers using noise [0.0]
  We present a quantum algorithm that uses noise as a resource. The goal of our quantum algorithm is the calculation of operator averages of an open quantum system evolving in time. We find that classes of open quantum systems exist where our algorithm performs very well, even with gate errors as high as 1%.
  arXiv  Detail & Related papers  (2022-10-21T17:47:32Z)
• Demonstration of algorithmic quantum speedup [0.0]
  An experimental demonstration of a provable algorithmic quantum speedup has remained elusive. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring. The speedup is observed on only one of the two QCs.
  arXiv  Detail & Related papers  (2022-07-15T17:59:47Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• Robustness Verification of Quantum Classifiers [1.3534683694551501]
  We define a formal framework for the verification and analysis of quantum machine learning algorithms against noises. A robust bound is derived and an algorithm is developed to check whether or not a quantum machine learning algorithm is robust with respect to quantum training data. Our approach is implemented on Google's Quantum classifier and can verify the robustness of quantum machine learning algorithms with respect to a small disturbance of noises.
  arXiv  Detail & Related papers  (2020-08-17T11:56:23Z)
• Quantum noise protects quantum classifiers against adversaries [120.08771960032033]
  Noise in quantum information processing is often viewed as a disruptive and difficult-to-avoid feature, especially in near-term quantum technologies. We show that by taking advantage of depolarisation noise in quantum circuits for classification, a robustness bound against adversaries can be derived. This is the first quantum protocol that can be used against the most general adversaries.
  arXiv  Detail & Related papers  (2020-03-20T17:56:14Z)

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.