Simpler Proofs of Quantumness

• URL: http://arxiv.org/abs/2005.04826v1
• Date: Mon, 11 May 2020 01:31:18 GMT
• Title: Simpler Proofs of Quantumness
• Authors: Zvika Brakerski and Venkata Koppula and Umesh Vazirani and Thomas Vidick
• Abstract summary: A proof of quantumness is a method for provably demonstrating that a quantum device can perform computational tasks that a classical device cannot. There are currently three approaches for exhibiting proofs of quantumness. We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function.
• Score: 16.12500804569801
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor's algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

Related papers

• Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
  A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass. Existing single-round protocols require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. We construct efficient single-round proofs of quantumness based on existing knowledge assumptions.
  arXiv  Detail & Related papers  (2024-05-24T17:33:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• 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)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• 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)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• 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)
• Advanced Equivalence Checking for Quantum Circuits [4.265279817927261]
  We propose an advanced methodology for equivalence checking of quantum circuits. We show that, by exploiting the reversibility of quantum circuits, complexity can be kept feasible. In contrast to the classical realm, simulation is very powerful in verifying quantum circuits.
  arXiv  Detail & Related papers  (2020-04-17T18:56:23Z)
• Forging quantum data: classically defeating an IQP-based quantum test [0.0]
  We describe a classical algorithm that can convince the verifier that the (classical) prover is quantum. We show that the key extraction algorithm is efficient in practice for problem sizes of hundreds of qubits.
  arXiv  Detail & Related papers  (2019-12-11T19:00:00Z)

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.