Hidden-State Proofs of Quantumness

• URL: http://arxiv.org/abs/2410.06368v1
• Date: Tue, 8 Oct 2024 21:04:53 GMT
• Title: Hidden-State Proofs of Quantumness
• Authors: Carl A. Miller,
• Abstract summary: An experimental cryptographic proof of quantumness will be a vital milestone in the progress of quantum information science. Error tolerance is a persistent challenge for implementing such tests. We present a proof of quantumness which maintains the same circuit structure as (Brakerski et al.)
• Score: 1.0878040851638
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: An experimental cryptographic proof of quantumness will be a vital milestone in the progress of quantum information science. Error tolerance is a persistent challenge for implementing such tests: we need a test that not only can be passed by an efficient quantum prover, but one that can be passed by a prover that exhibits a certain amount of computational error. (Brakerski et al. 2018) introduced an innovative two-round proof of quantumness based on the Learning With Errors (LWE) assumption. However, one of the steps in their protocol (the pre-image test) has low tolerance for error. In this work we present a proof of quantumness which maintains the same circuit structure as (Brakerski et al. 2018) while improving the robustness for noise. Our protocol is based on cryptographically hiding an extended Greenberger-Horne-Zeilinger (GHZ) state within a sequence of classical bits. Asymptotically, our protocol allows the total probability of error within the circuit to be as high as $1 - O ( \lambda^{-C} )$, where $\lambda$ is the security parameter and $C$ is a constant that can be made arbitrarily large. As part of the proof of this result, we also prove an uncertainty principle over finite abelian groups which may be of independent interest.

Related papers

• 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)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Error statistics and scalability of quantum error mitigation formulas [4.762232147934851]
  We apply statistics principles to quantum error mitigation and analyse the scaling behaviour of its intrinsic error. We find that the error increases linearly $O(epsilon N)$ with the gate number $N$ before mitigation and sub-linearly $O(epsilon' Ngamma)$ after mitigation. The $sqrtN$ scaling is a consequence of the law of large numbers, and it indicates that error mitigation can suppress the error by a larger factor in larger circuits.
  arXiv  Detail & Related papers  (2021-12-12T15:02:43Z)
• Towards Demonstrating Fault Tolerance in Small Circuits Using Bacon-Shor Codes [5.352699766206807]
  We study a next step - fault-tolerantly implementing quantum circuits. We compute pseudo-thresholds for the Pauli error rate $p$ in a depolarizing noise model. We see that multiple rounds of stabilizer measurements give an improvement over performing a single round at the end.
  arXiv  Detail & Related papers  (2021-08-04T14:24:14Z)
• 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 Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  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.
  arXiv  Detail & Related papers  (2020-05-11T01:31:18Z)

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.