arXiv:1306.3200

Synthesis of unitaries with Clifford+T circuits

Vadym Kliuchnikov

Published Jun 13, 2013• 24 citations

Abstract

We describe a new method for approximating an arbitrary $n$ qubit unitary with precision $\varepsilon$ using a Clifford and T circuit with $O(4^{n}n(\log(1/\varepsilon)+n))$ gates. The method is based on rounding off a unitary to a unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ and employing exact synthesis. We also show that any $n$ qubit unitary over the ring $\mathbb{Z}[i,1/\sqrt{2}]$ with entries of the form $(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}$ can be exactly synthesized using $O(4^{n}nk)$ Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring $O(3^{2^{n}}nk)$ elementary gates.

DOI: 10.48550/arxiv.1306.3200

Related papers

The exact synthesis of 1- and 2-qubit Clifford+T circuits

Travis B. Russell

arXiv:1408.6202Aug 22, 20142 citations

Exact synthesis of multiqubit Clifford+ T circuits

Brett Gordon Giles, Peter Selinger

arXiv:1212.0506Physical Review AMar 26, 2013162 citations

Multi-qubit circuit synthesis and Hermitian lattices

Vadym Kliuchnikov, Sebastian Schönnenbeck

arXiv:2405.19302May 29, 20240 citations

Matchgate synthesis via Clifford matchgates and $T$ gates

Berta Casas, Paolo Braccia, Élie Gouzien +2 more

quant-pharXiv:2602.05425Feb 6, 20260 citations

Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

Vadym Kliuchnikov, Maslov, Dmitri, Michele Mosca

arXiv:1206.5236Jun 22, 201257 citations

Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

Quantum Information and ComputationMay 1, 2013146 citations

arXiv:1306.3200

Synthesis of unitaries with Clifford+T circuits

Vadym Kliuchnikov

Published Jun 13, 2013• 24 citations

arXiv HTML PDF

Abstract

We describe a new method for approximating an arbitrary

n

qubit unitary with precision

\varepsilon

using a Clifford and T circuit with

O(4^{n}n(\log(1/\varepsilon)+n))

gates. The method is based on rounding off a unitary to a unitary over the ring

\mathbb{Z}[i,1/\sqrt{2}]

and employing exact synthesis. We also show that any

n

qubit unitary over the ring

\mathbb{Z}[i,1/\sqrt{2}]

with entries of the form

(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}

can be exactly synthesized using

O(4^{n}nk)

Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring

O(3^{2^{n}}nk)

elementary gates.

DOI: 10.48550/arxiv.1306.3200

Related papers

The exact synthesis of 1- and 2-qubit Clifford+T circuits

Travis B. Russell

We describe a new method for the decomposition of an arbitrary $n$ qubit operator with entries in $\mathbb{Z}[i,\frac{1}{\sqrt{2}}]$ , i.e., of the form $(a+b\sqrt{2}+i(c+d\sqrt{2}))/{\sqrt{2}^{k}}$ , into Clifford+ $T$ operators where $n\le 2$ . This method achieves a bound of $O(k)$ gates using at most one ancilla using decomposition into $1$ - and $2$ -level matrices which was first proposed by Giles and Selinger.We describe a new method for the decomposition of an arbitrary $n$ qubit operator with entries in $\mathbb{Z}[i,\frac{1}{\sqrt{2}}]$, i.e., of the form $(a+b\sqrt{2}+i(c+d\sqrt{2}))/{\sqrt{2}^{k}}$, into Clifford+$T$ operators where $n\le 2$. This method achieves a bound of $O(k)$ gates using at most one ancilla using decomposition into $1$- and $2$-level matrices which was first proposed by Giles and Selinger.

arXiv:1408.6202Aug 22, 20142 citations

Exact synthesis of multiqubit Clifford+ T circuits

Brett Gordon Giles, Peter Selinger

We prove that a unitary matrix has an exact representation over the Clifford+ $T$ gate set with local ancillas if and only if its entries are in the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ . Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+ $T$ circuit from any such $n$ -qubit operator. We also characterize the Clifford+ $T$ operators that can be represented without ancillas.We prove that a unitary matrix has an exact representation over the Clifford+$T$ gate set with local ancillas if and only if its entries are in the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$. Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+$T$ circuit from any such $n$-qubit operator. We also characterize the Clifford+$T$ operators that can be represented without ancillas.

arXiv:1212.0506Physical Review AMar 26, 2013162 citations

Multi-qubit circuit synthesis and Hermitian lattices

Vadym Kliuchnikov, Sebastian Schönnenbeck

We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$ . The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.

arXiv:2405.19302May 29, 20240 citations

Matchgate synthesis via Clifford matchgates and $T$ gates

Berta Casas, Paolo Braccia, Élie Gouzien +2 more

Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford $+T$ . Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the $\overline{T}$ gate (a $T$ unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between $n$ -qubit matchgate circuits and the standard representation of $\mathbb{SO}(2n)$ , which reduces the compilation from $2^n\times 2^n$ unitaries to $2n\times2n$ ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error $\varepsilon_{\mathbb{SO}(2n)}$ incurred in this smaller-dimensional representation translates at most into an $O(n \,\varepsilon_{\mathbb{SO}(2n)})$ error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries $U$ such that $U\otimes U^*$ has entries in the ring $\mathbb{Z}\big[1/\sqrt 2,i\big]$ can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford $+\overline{T}$ set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic $XX$ Hamiltonian on $n=4,\,8$ qubits.Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford$+T$. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the $\overline{T}$ gate (a $T$ unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between $n$-qubit matchgate circuits and the standard representation of $\mathbb{SO}(2n)$, which reduces the compilation from $2^n\times 2^n$ unitaries to $2n\times2n$ ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error $\varepsilon_{\mathbb{SO}(2n)}$ incurred in this smaller-dimensional representation translates at most into an $O(n \,\varepsilon_{\mathbb{SO}(2n)})$ error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries $U$ such that $U\otimes U^*$ has entries in the ring $\mathbb{Z}\big[1/\sqrt 2,i\big]$ can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford$+\overline{T}$ set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic $XX$ Hamiltonian on $n=4,\,8$ qubits.

quant-pharXiv:2602.05425Feb 6, 20260 citations

Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

Vadym Kliuchnikov, Maslov, Dmitri, Michele Mosca

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ , in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$ -qubit case.In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.

arXiv:1206.5236Jun 22, 201257 citations

Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates

Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ , in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$ -qubit case.In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.

Quantum Information and ComputationMay 1, 2013146 citations

We describe a new method for approximating an arbitrary

n

qubit unitary with precision

\varepsilon

using a Clifford and T circuit with

O(4^{n}n(\log(1/\varepsilon)+n))

gates. The method is based on rounding off a unitary to a unitary over the ring

\mathbb{Z}[i,1/\sqrt{2}]

and employing exact synthesis. We also show that any

n

qubit unitary over the ring

\mathbb{Z}[i,1/\sqrt{2}]

with entries of the form

(a+b\sqrt{2}+ic+id\sqrt{2})/2^{k}

can be exactly synthesized using

O(4^{n}nk)

Clifford and T gates using two ancillary qubits. This new exact synthesis algorithm is an improvement over the best known exact synthesis method by B. Giles and P. Selinger requiring

O(3^{2^{n}}nk)

elementary gates.

We describe a new method for the decomposition of an arbitrary

n

qubit operator with entries in

\mathbb{Z}[i,\frac{1}{\sqrt{2}}]

, i.e., of the form

(a+b\sqrt{2}+i(c+d\sqrt{2}))/{\sqrt{2}^{k}}

, into Clifford+

T

operators where

n\le 2

. This method achieves a bound of

O(k)

gates using at most one ancilla using decomposition into

1

- and

2

-level matrices which was first proposed by Giles and Selinger.

We prove that a unitary matrix has an exact representation over the Clifford+

T

gate set with local ancillas if and only if its entries are in the ring

\mathbb{Z}[\frac{1}{\sqrt{2}},i]

. Moreover, we show that one ancilla always suffices. These facts were conjectured by Kliuchnikov, Maslov, and Mosca. We obtain an algorithm for synthesizing a exact Clifford+

T

circuit from any such

n

-qubit operator. We also characterize the Clifford+

T

operators that can be represented without ancillas.

We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in

\mathbb{Z}[i,1/\sqrt{2}]

. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.

+T

. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the

\overline{T}

gate (a

T

unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between

n

-qubit matchgate circuits and the standard representation of

\mathbb{SO}(2n)

, which reduces the compilation from

2^n\times 2^n

unitaries to

2n\times2n

ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error

\varepsilon_{\mathbb{SO}(2n)}

incurred in this smaller-dimensional representation translates at most into an

O(n \,\varepsilon_{\mathbb{SO}(2n)})

error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries

U

such that

U\otimes U^*

has entries in the ring

\mathbb{Z}\big[1/\sqrt 2,i\big]

can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford

+\overline{T}

set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic

XX

Hamiltonian on

n=4,\,8

qubits.

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring

\mathbb{Z}[\frac{1}{\sqrt{2}},i]

, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring

\mathbb{Z}[\frac{1}{\sqrt{2}},i]

holds in the

n

-qubit case.

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring

\mathbb{Z}[\frac{1}{\sqrt{2}},i]

, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring

\mathbb{Z}[\frac{1}{\sqrt{2}},i]

holds in the

n

-qubit case.