Quantum Proofs of Proximity

• URL: http://arxiv.org/abs/2105.03697v2
• Date: Fri, 7 Oct 2022 16:33:19 GMT
• Title: Quantum Proofs of Proximity
• Authors: Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
• Abstract summary: We show that QMA proofs of proximity can be exponentially stronger than classical proofs of proximity and quantum testers. Our results include an algorithmic framework that enables quantum speedups for testing an expressive class of properties. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family.
• Score: 6.160793572747927
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject inputs that are $\varepsilon$-far from $\Pi$, while only probing a minuscule portion of their input. We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016). Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. A consequence of this framework is a QMA algorithm to verify the Parity of an $n$-bit string with $O(n^{2/3})$ queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.

Related papers

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  We propose a new technique for proving lower bounds on the quantum query of unitary property testing. All obtained lower bounds hold for any $mathsfC$-tester with $mathsfC subseteq mathsfQMA(2)/mathsfqpoly$. We show that there exist quantum oracles relative to which $mathsfQMA(2) notsupset mathsfSBQP$ and $mathsfQMA/mathsfqpoly
  arXiv  Detail & Related papers  (2024-01-15T19:00:36Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  We study the impact of quantum computation on the fundamental problem of testing the property of distributions. We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
  arXiv  Detail & Related papers  (2023-02-13T04:03:59Z)
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
  We introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM) We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code.
  arXiv  Detail & Related papers  (2022-11-08T01:36:02Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Implementing Quantum Finite Automata Algorithms on Noisy Devices [0.0]
  We present improved circuit based implementations for QFA algorithms recognizing the $ MOD_p $ problem using the Qiskit framework. We run the circuits on real IBM quantum devices but due to the limitation of the real quantum devices in the NISQ era, the results are heavily affected by the noise.
  arXiv  Detail & Related papers  (2021-05-13T10:51:28Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

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.