A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits

• URL: http://arxiv.org/abs/2407.11152v3
• Date: Mon, 12 Aug 2024 11:20:08 GMT
• Title: A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits
• Authors: Matthew Amy, Neil J. Ross, Scott Wesley,
• Abstract summary: We give a complete equational theory for 3-qubit quantum circuits over the Toffoli-Hadamard gate set X, CX, CCX, H .
• Score: 0.8192907805418581
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a sound and complete equational theory for 3-qubit quantum circuits over the Toffoli-Hadamard gate set { X, CX, CCX, H }. That is, we introduce a collection of true equations among Toffoli-Hadamard circuits on three qubits that is sufficient to derive any other true equation between such circuits. To obtain this equational theory, we first consider circuits over the Toffoli-K gate set { X, CX, CCX, K }, where K = HxH. The Toffoli-Hadamard and Toffoli-K gate sets appear similar, but they are crucially different on exactly three qubits. Indeed, in this case, the former generates an infinite group of operators, while the latter generates the finite group of automorphisms of the well-known E8 lattice. We take advantage of this fact, and of the theory of automorphism groups of lattices, to obtain a sound and complete collection of equations for Toffoli-K circuits. We then extend this equational theory to one for Toffoli-Hadamard circuits by leveraging prior work of Li et al. on Toffoli-Hadamard operators.

Related papers

• A Complete Equational Theory for Real-Clifford+CH Quantum Circuits [51.56484100374058]
  We give a simple set of equalities between circuits of this fragment, and prove that any other true equation can be derived from these.<n>This is the first such completeness result for a finitely-generated, universal fragment of quantum circuits, with no parameterized gates and no need for ancillas.
  arXiv  Detail & Related papers  (2026-02-06T12:11:39Z)
• Prefix Sums via Kronecker Products [47.600794349481966]
  We show how to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.<n>As an application, we show how to use these circuits to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.
  arXiv  Detail & Related papers  (2025-12-18T08:49:18Z)
• Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals [6.252607743959949]
  We construct a family of distributions $mathcalD_nn$ with $mathcalD_n$ over $0, 1n$ and a family of depth-$7$ quantum circuits.<n>Our family of distributions is inspired by the Parity Halving Problem of Watts, Kothari, Schaeffer, and Tal (STOC, 2019), which built on work of Bravyi, Gosset, and K"onig (Science), to separate shallow quantum and classical circuits for relational problems.
  arXiv  Detail & Related papers  (2025-10-09T05:34:42Z)
• EQB: Synthesizing Permutative Quantum Gates and Circuits Using Rotation-Based Group Decomposition [0.0]
  The decomposition from the group theory-based methods of Sasao and Saraivanov is extended to design binary quantum cascades. A class of local transformations is also presented to simplify the final canonical cascade circuits.
  arXiv  Detail & Related papers  (2024-10-25T00:34:14Z)
• Toffoli gates solve the tetrahedron equations [1.8434042562191815]
  In particular, factorised scattering operators result in integrable quantum circuits that provide universal quantum computation. A natural question is to extend this construction to higher qubit gates, like the Toffoli gates. We show that unitary families of such operators are constructed by the 3-dimensional generalizations of the Yang-Baxter operators.
  arXiv  Detail & Related papers  (2024-05-26T08:03:24Z)
• Quantum circuit model for discrete-time three-state quantum walks on Cayley graphs [0.0]
  We develop qutrit circuit models for discrete-time three-state quantum walks on Cayley graphs. We numerically simulate these circuits to mimic its performance on noisy quantum computers.
  arXiv  Detail & Related papers  (2024-01-19T20:45:26Z)
• The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality [0.0]
  We show how to generalise all the phase-free qudit rules to qudits. We prove that circuits of |0>-controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d.
  arXiv  Detail & Related papers  (2023-07-19T16:09:48Z)
• Third quantization of open quantum systems: new dissipative symmetries and connections to phase-space and Keldysh field theory formulations [77.34726150561087]
  We reformulate the technique of third quantization in a way that explicitly connects all three methods. We first show that our formulation reveals a fundamental dissipative symmetry present in all quadratic bosonic or fermionic Lindbladians. For bosons, we then show that the Wigner function and the characteristic function can be thought of as ''wavefunctions'' of the density matrix.
  arXiv  Detail & Related papers  (2023-02-27T18:56:40Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• A Complete Equational Theory for Quantum Circuits [58.720142291102135]
  We introduce the first complete equational theory for quantum circuits. Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
  arXiv  Detail & Related papers  (2022-06-21T17:56:31Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Crossing with the circle in Dijkgraaf-Witten theory and applications to topological phases of matter [0.0]
  We compute these conditions for the 4-3-2-1 Dijkgraaf-Witten theory. In the context of the lattice Hamiltonian realisation of the theory, the quantum invariants assigned to the circle and the torus encode the defect open string-like and bulk loop-like excitations.
  arXiv  Detail & Related papers  (2021-03-23T17:37:24Z)
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits [69.43216268165402]
  QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits. It is based on Google Cirq and is developed with Clifford+T circuits in mind. For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
  arXiv  Detail & Related papers  (2020-07-21T15:36:25Z)

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.