Gottesman Types for Quantum Programs

• URL: http://arxiv.org/abs/2109.02197v1
• Date: Mon, 6 Sep 2021 01:02:01 GMT
• Title: Gottesman Types for Quantum Programs
• Authors: Robert Rand (University of Chicago), Aarthi Sundaram (Microsoft Quantum), Kartik Singhal (University of Chicago), Brad Lackey (Microsoft Quantum and University of Maryland)
• Abstract summary: We show that Gottesman's semantics for quantum programs can be treated as a type system. We also show that it can be extended beyond the Clifford set to partially characterize a broad range of programs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Heisenberg representation of quantum operators provides a powerful technique for reasoning about quantum circuits, albeit those restricted to the common (non-universal) Clifford set H, S and CNOT. The Gottesman-Knill theorem showed that we can use this representation to efficiently simulate Clifford circuits. We show that Gottesman's semantics for quantum programs can be treated as a type system, allowing us to efficiently characterize a common subset of quantum programs. We also show that it can be extended beyond the Clifford set to partially characterize a broad range of programs. We apply these types to reason about separable states and the superdense coding algorithm.

Related papers

• Clifford and Non-Clifford Splitting in Quantum Circuits: Applications and ZX-Calculus Detection Procedure [49.1574468325115]
  We propose and analyze use cases that come from quantum circuits that can be written as product between a Clifford and a Non-Clifford unitary. We make use of ZX-Calculus and its assets to detect a limiting border of these circuits that would allow for a separation between a Clifford section and a Non-Clifford section.
  arXiv  Detail & Related papers  (2025-04-22T16:10:34Z)
• An explicit tensor notation for quantum computing [0.0]
  This paper introduces a formalism that aims to describe the intricacies of quantum computation. The focus is on providing a comprehensive representation of quantum states for multiple qubits and the quantum gates that manipulate them.
  arXiv  Detail & Related papers  (2024-09-16T17:21:17Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Hybrid Quantum-Classical Machine Learning with String Diagrams [49.1574468325115]
  This paper develops a formal framework for describing hybrid algorithms in terms of string diagrams. A notable feature of our string diagrams is the use of functor boxes, which correspond to a quantum-classical interfaces.
  arXiv  Detail & Related papers  (2024-07-04T06:37:16Z)
• On Classical Simulation of Quantum Circuits Composed of Clifford Gates [0.0]
  The Gottesman-Knill theorem asserts that quantum circuits composed solely of Clifford gates can be efficiently simulated classically. In this work, we break down the step-by-step procedure of the Gottesman-Knill theorem in a beginner-friendly manner.
  arXiv  Detail & Related papers  (2024-05-22T12:36:15Z)
• Quantum Recursive Programming with Quantum Case Statements [8.320147245667124]
  A simple programming language for supporting this kind of quantum recursion is defined. A series of examples are presented to show that some quantum algorithms can be elegantly written as quantum recursion programs.
  arXiv  Detail & Related papers  (2023-11-03T05:44:52Z)
• 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)
• Towards a SAT Encoding for Quantum Circuits: A Journey From Classical Circuits to Clifford Circuits and Beyond [3.610459670994051]
  We propose a propositional SAT encoding that can be applied to arbitrary quantum circuits. We show that due to the inherent complexity of representing quantum states, constructing such an encoding is not feasible in general. We explicitly demonstrate how the proposed encoding can be applied to the class of Clifford circuits as a representative.
  arXiv  Detail & Related papers  (2022-03-01T19:00:02Z)
• 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)
• Quantum Hoare Type Theory: Extended Abstract [0.0]
  In quantum computing, formal verification and sound static type systems prevent several classes of bugs from being introduced. We propose Quantum Hoare Types by extending the Quantum IO Monad by indexing it with pre- and post-conditions that serve as program specifications. QHTT has the potential to be a unified system for programming, specifying, and reasoning about quantum programs.
  arXiv  Detail & Related papers  (2021-09-06T01:02:20Z)
• 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)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48: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.