Hadamard-$Π$: Equational Quantum Programming

• URL: http://arxiv.org/abs/2506.06835v1
• Date: Sat, 07 Jun 2025 15:26:33 GMT
• Title: Hadamard-$Π$: Equational Quantum Programming
• Authors: Wang Fang, Chris Heunen, Robin Kaarsgaard,
• Abstract summary: We introduce a small quantum programming language extending the universal classical reversible programming language $Pi$ with a single primitive corresponding to the Hadamard gate.<n>The language comes equipped with a sound and complete categorical semantics that is specified by a purely equational theory.
• Score: 0.5852077003870417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum computing offers advantages over classical computation, yet the precise features that set the two apart remain unclear. In the standard quantum circuit model, adding a 1-qubit basis-changing gate -- commonly chosen to be the Hadamard gate -- to a universal set of classical reversible gates yields computationally universal quantum computation. However, the computational behaviours enabled by this addition are not fully characterised. We give such a characterisation by introducing a small quantum programming language extending the universal classical reversible programming language $\Pi$ with a single primitive corresponding to the Hadamard gate. The language comes equipped with a sound and complete categorical semantics that is specified by a purely equational theory, enabling reasoning about the equivalence of quantum programs in a way that can be automated. Completeness is shown by means of a novel finite presentation, and corresponding synthesis algorithm, for the groups of orthogonal matrices with entries in the ring $\mathbb{Z}[\tfrac{1}{\sqrt{2}}]$.

Related papers

• Fermionic anyons: entanglement and quantum computation from a resource-theoretic perspective [39.58317527488534]
  We develop a framework to characterize the separability of a specific type of one-dimensional quasiparticle known as a fermionic anyon. We map this notion of fermionic-anyon separability to the free resources of matchgate circuits. We also identify how entanglement between two qubits encoded in a dual-rail manner, as standard for matchgate circuits, corresponds to the notion of entanglement between fermionic anyons.
  arXiv  Detail & Related papers  (2023-06-01T15:25:19Z)
• Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform [0.0]
  We present a transparent algorithm for implementing the qubit quantum Schur transform. We study the associated Schur states, which consist of qubits coupled via Clebsch-Gordan coefficients. It is shown that Wigner 6-j symbols and SU(N) Clebsch-Gordan coefficients naturally fit our framework.
  arXiv  Detail & Related papers  (2023-05-06T15:19:52Z)
• Quantum Circuit Completeness: Extensions and Simplifications [44.99833362998488]
  The first complete equational theory for quantum circuits has only recently been introduced. We simplify the equational theory by proving that several rules can be derived from the remaining ones. The complete equational theory can be extended to quantum circuits with ancillae or qubit discarding.
  arXiv  Detail & Related papers  (2023-03-06T13:31:27Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• 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)
• Qunity: A Unified Language for Quantum and Classical Computing (Extended Version) [3.862247454265945]
  We introduce Qunity, a new quantum programming language.<n>Qunity treats quantum computing as a natural generalization of classical computing.<n>We show how Qunity can cleanly express several quantum algorithms.
  arXiv  Detail & Related papers  (2022-04-26T15:34:22Z)
• LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits [58.720142291102135]
  We introduce the LOv-calculus, a graphical language for reasoning about linear optical quantum circuits. Two LOv-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LOv-calculus.
  arXiv  Detail & Related papers  (2022-04-25T16:59:26Z)
• Automatic quantum circuit encoding of a given arbitrary quantum state [0.0]
  We propose a quantum-classical hybrid algorithm to encode a given arbitrarily quantum state onto an optimal quantum circuit. The proposed algorithm employs as an objective function the absolute value of fidelity $F = langle 0 vert hatmathcalCdagger vert Psi rangle$. We experimentally demonstrate that a quantum circuit generated by the AQCE algorithm can indeed represent the original quantum state reasonably on a noisy real quantum device.
  arXiv  Detail & Related papers  (2021-12-29T12:33:41Z)
• 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 simulation of $\phi^4$ theories in qudit systems [53.122045119395594]
  We discuss the implementation of quantum algorithms for lattice $Phi4$ theory on circuit quantum electrodynamics (cQED) system. The main advantage of qudit systems is that its multi-level characteristic allows the field interaction to be implemented only with diagonal single-qudit gates.
  arXiv  Detail & Related papers  (2021-08-30T16:30:33Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
  arXiv  Detail & Related papers  (2021-06-06T13:15:25Z)
• Universal quantum computation via quantum controlled classical operations [0.0]
  A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. We show that even a primitive computer capable of implementing only SWAP gates, can be lifted to universal quantum computing.
  arXiv  Detail & Related papers  (2021-04-13T18:00:13Z)
• Quantum circuit design for universal distribution using a superposition of classical automata [2.4192504570921622]
  This circuit is able to accelerate the inference of algorithmic structures in data for discovering causal generative models. A classical exhaustive enumeration of all possible programs on the automata is shown for a couple of example cases. This is the first time, a superposition of classical automata is implemented on the circuit model of quantum computation.
  arXiv  Detail & Related papers  (2020-06-01T14:47:28Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.