IQP Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security

• URL: http://arxiv.org/abs/2308.07152v1
• Date: Mon, 14 Aug 2023 14:03:33 GMT
• Title: IQP Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
• Authors: Michael J. Bremner, Bin Cheng and Zhengfeng Ji
• Abstract summary: We introduce a family of IQP sampling protocols called the emphstabilizer scheme, which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP circuit correlation functions. To assess classical security, we explore a class of attacks based on secret extraction, including the Kahanamoku-Meyer's attack as a special case.
• Score: 1.7586417032126085
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling problems demonstrating beyond classical computing power with noisy intermediate-scale quantum (NISQ) devices have been experimentally realized. In those realizations, however, our trust that the quantum devices faithfully solve the claimed sampling problems is usually limited to simulations of smaller-scale instances and is, therefore, indirect. The problem of verifiable quantum advantage aims to resolve this critical issue and provides us with greater confidence in a claimed advantage. Instantaneous quantum polynomial-time (IQP) sampling has been proposed to achieve beyond classical capabilities with a verifiable scheme based on quadratic-residue codes (QRC). Unfortunately, this verification scheme was recently broken by an attack proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable quantum advantage by making two major contributions. Firstly, we introduce a family of IQP sampling protocols called the \emph{stabilizer scheme}, which builds on results linking IQP circuits, the stabilizer formalism, coding theory, and an efficient characterization of IQP circuit correlation functions. This construction extends the scope of existing IQP-based schemes while maintaining their simplicity and verifiability. Secondly, we introduce the \emph{Hidden Structured Code} (HSC) problem as a well-defined mathematical challenge that underlies the stabilizer scheme. To assess classical security, we explore a class of attacks based on secret extraction, including the Kahanamoku-Meyer's attack as a special case. We provide evidence of the security of the stabilizer scheme, assuming the hardness of the HSC problem. We also point out that the vulnerability observed in the original QRC scheme is primarily attributed to inappropriate parameter choices, which can be naturally rectified with proper parameter settings.

Related papers

• Reinforcement learning-assisted quantum architecture search for variational quantum algorithms [0.0]
  This thesis focuses on identifying functional quantum circuits in noisy quantum hardware. We introduce a tensor-based quantum circuit encoding, restrictions on environment dynamics to explore the search space of possible circuits efficiently. In dealing with various VQAs, our RL-based QAS outperforms existing QAS.
  arXiv  Detail & Related papers  (2024-02-21T12:30:39Z)
• Secret extraction attacks against obfuscated IQP circuits [0.92463347238923]
  In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of IQP circuits. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test. Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol.
  arXiv  Detail & Related papers  (2023-12-15T19:08:35Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• 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)
• Learning Classical Readout Quantum PUFs based on single-qubit gates [9.669942356088377]
  We formalize the class of Classical Readout Quantum PUFs (CR-QPUFs) using the statistical query (SQ) model. We show insufficient security for CR-QPUFs based on singlebit rotation gates, when adversary has SQ access to the CR-QPUF. We demonstrate how a malicious party can learn CR-QPUF characteristics and forge the signature of a quantum device.
  arXiv  Detail & Related papers  (2021-12-13T13:29:22Z)
• Indistinguishability Obfuscation of Null Quantum Circuits and Applications [17.72516323214125]
  We study the notion of indistinguishability obfuscation for null quantum circuits (quantum null-iO) We show how quantum null-iO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making assumptions.
  arXiv  Detail & Related papers  (2021-06-11T00:08:14Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)
• 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)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

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.