Improved synthesis of Toffoli-Hadamard circuits

DOI10.1007/978-3-031-38100-3_12MaRDI QIDQ6148121zbMATH OpenFDO

Authors Matthew Amy, Andrew N. Glaudell, Sarah Meng Li, Neil J. Ross

Publication date 11 January 2024

Published in Reversible Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.11305

zbMATH Keywords

exact synthesisquantum circuitsToffoli-Hadamard

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Abstract: The matrices that can be exactly represented by a circuit over the Toffoli-Hadamard gate set are the orthogonal matrices of the form $M/sqrt2{}^k$, where $M$ is an integer matrix and $k$ is a nonnegative integer. The exact synthesis problem for this gate set is the problem of constructing a circuit for a given such matrix. Existing methods produce circuits consisting of $O(2^{n}log(n)k)$ gates, where $n$ is the dimension of the matrix. In this paper, we provide two improved synthesis methods. First, we show that a technique introduced by Kliuchnikov in 2013 for Clifford+$T$ circuits can be straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity of the synthesized circuit from $O(2^{n}log(n)k)$ to $O(n^{2}log(n)k)$. Then, we present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits. Our results also apply to orthogonal matrices over the dyadic fractions, which correspond to circuits using the 2-qubit gate $HotimesH$, rather than the usual single-qubit Hadamard gate $H$.

Recommendations

• Quantum circuit optimization by Hadamard gate reduction
• Advanced exact synthesis of Clifford+T circuits
• Quantum circuits synthesis using Householder transformations
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• Optimal synthesis of linear reversible circuits

Cites work

• Advanced exact synthesis of Clifford+T circuits
• Both Toffoli and Controlled-NOT need little help to universal quantum computing
• Conservative logic
• Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets
• scientific article; zbMATH DE number 7449988 (Why is no real title available?)
• The Toffoli-Hadamard gate system: an algebraic approach

Cited in

(4)

• Exact synthesis of multiqubit Clifford-cyclotomic circuits
• Multi-controlled phase gate synthesis with ZX-calculus applied to neutral atom hardware
• Exact synthesis of multiqutrit Clifford-cyclotomic circuits
• A sound and complete equational theory for 3-qubit Toffoli-Hadamard circuits

This page was built for publication: Improved synthesis of Toffoli-Hadamard circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148121)