Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0606061

Simplifying Quantum Circuits via Circuit Invariants and Dressed CNOTs

Robert R. Tucci

Published Jun 7, 2006• 1 citation
arXivHTMLPDF

Abstract

Quantum Compiling Algorithms decompose (exactly, without approximations) an arbitrary $2^\nb$ unitary matrix acting on $\nb$ qubits, into a sequence of elementary operations (SEO). There are many possible ways of decomposing a unitary matrix into a SEO, and some of these decompositions have shorter length (are more efficient) than others. Finding an optimum (shortest) decomposition is a very hard task, and is not our intention here. A less ambitious, more doable task is to find methods for optimizing small segments of a SEO. Call these methods piecewise optimizations. Piecewise optimizations involve replacing a small quantum circuit by an equivalent one with fewer CNOTs. Two circuits are said to be equivalent if one of them multiplied by some external local operations equals the other. This equivalence relation between circuits has its own class functions, which we call circuit invariants. Dressed CNOTs are a simple yet very useful generalization of standard CNOTs. After discussing circuit invariants and dressed CNOTs, we give some methods for simplifying 2-qubit and 3-qubit circuits. We include with this paper software (written in Octave/Matlab) that checks many of the algorithms proposed in the paper.

DOI
10.48550/arxiv.quant-ph/0606061

Related papers

Quantum Compiling with Approximation of Multiplexors

Robert R. Tucci

A quantum compiling algorithm is an algorithm for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). Suppose $U_{in}$ is an $\nb$-bit unstructured unitary matrix (a unitary matrix with no special symmetries) that we wish to compile. For $\nb>10$, expressing $U_{in}$ as a SEO requires more than a million CNOTs. This calls for a method for finding a unitary matrix that: (1)approximates $U_{in}$ well, and (2) is expressible with fewer CNOTs than $U_{in}$. The purpose of this paper is to propose one such approximation method. Various quantum compiling algorithms have been proposed in the literature that decompose an arbitrary unitary matrix into a sequence of U(2)-multiplexors, each of which is then decomposed into a SEO. Our strategy for approximating $U_{in}$ is to approximate these intermediate U(2)-multiplexors. In this paper, we will show how one can approximate a U(2)-multiplexor by another U(2)-multiplexor that is expressible with fewer CNOTs.

arXiv:quant-ph/0412072•Dec 9, 2004•1 citation

Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers

Anna M. Krol, Aritra Sarkar, Imran Ashraf +2 more

Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.

arXiv:2101.02993•Applied Sciences•Jan 12, 2022•54 citations

How to Compile Some NAND Formula Evaluators

Robert R. Tucci

We say a unitary operator acting on a set of qubits has been compiled if it has been expressed as a SEO (sequence of elementary operations, like CNOTs and single-qubit operations). SEO's are often represented as quantum circuits. arXiv:quant-ph/0702144 by Farhi-Goldstone-Gutmann has inspired a recent flurry of papers, that propose quantum algorithms for evaluating NAND formulas via quantum walks over tree graphs. These algorithms use two types of unitary evolution: oracle and non-oracle. Non-oracle evolutions are independent of the NAND formula input, whereas oracle evolutions depend on this input. In this paper we compile (i.e., give explicit SEOs and their associated quantum circuits for) the oracle and non-oracle evolution operators used in some of these NAND formula evaluators. We consider here only the case of balanced binary NAND trees. Our compilation methods are based on the CSD (Cosine Sine Decomposition), a matrix decomposition from Linear Algebra. The CS decomposition has been used very successfully in the past to compile unstructured unitary matrices exactly.

arXiv:0706.0479•Jun 4, 2007•5 citations

Qubiter Algorithm Modification, Expressing Unstructured Unitary Matrices with Fewer CNOTs

Robert R. Tucci

A quantum compiler is a software program for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). The author of this paper is also the author of a quantum compiler called Qubiter. Qubiter uses a matrix decomposition called the Cosine-Sine Decomposition (CSD) that is well known in the field of Computational Linear Algebra. One way of measuring the efficiency of a quantum compiler is to measure the number of CNOTs it uses to express an unstructured unitary matrix (a unitary matrix with no special symmetries). We will henceforth refer to this number as $ε$. In this paper, we show how to improve $ε$ for Qubiter so that it matches the current world record for $ε$, which is held by another quantum compiling algorithm based on CSD.

arXiv:quant-ph/0411027•Nov 3, 2004•6 citations

Finding small two-qubit circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 24, 2004•13 citations

Compiling Quantum Circuits using the Palindrome Transform

Alfred V. Aho, Krysta M. Svore

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2^n x 2^n unitary matrices into efficient circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of self-inverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an numerative algorithm for minimal (n-1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates.

arXiv:quant-ph/0311008•Nov 3, 2003•18 citations
Quantum Compiling Algorithms decompose (exactly, without approximations) an arbitrary 2\nb2^\nb2\nb unitary matrix acting on \nb\nb\nb qubits, into a sequence of elementary operations (SEO). There are many possible ways of decomposing a unitary matrix into a SEO, and some of these decompositions have shorter length (are more efficient) than others. Finding an optimum (shortest) decomposition is a very hard task, and is not our intention here. A less ambitious, more doable task is to find methods for optimizing small segments of a SEO. Call these methods piecewise optimizations. Piecewise optimizations involve replacing a small quantum circuit by an equivalent one with fewer CNOTs. Two circuits are said to be equivalent if one of them multiplied by some external local operations equals the other. This equivalence relation between circuits has its own class functions, which we call circuit invariants. Dressed CNOTs are a simple yet very useful generalization of standard CNOTs. After discussing circuit invariants and dressed CNOTs, we give some methods for simplifying 2-qubit and 3-qubit circuits. We include with this paper software (written in Octave/Matlab) that checks many of the algorithms proposed in the paper.
A quantum compiling algorithm is an algorithm for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). Suppose UinU_{in}Uin​ is an $\nb$-bit unstructured unitary matrix (a unitary matrix with no special symmetries) that we wish to compile. For $\nb>10$, expressing UinU_{in}Uin​ as a SEO requires more than a million CNOTs. This calls for a method for finding a unitary matrix that: (1)approximates UinU_{in}Uin​ well, and (2) is expressible with fewer CNOTs than UinU_{in}Uin​. The purpose of this paper is to propose one such approximation method. Various quantum compiling algorithms have been proposed in the literature that decompose an arbitrary unitary matrix into a sequence of U(2)-multiplexors, each of which is then decomposed into a SEO. Our strategy for approximating UinU_{in}Uin​ is to approximate these intermediate U(2)-multiplexors. In this paper, we will show how one can approximate a U(2)-multiplexor by another U(2)-multiplexor that is expressible with fewer CNOTs.
Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.
We say a unitary operator acting on a set of qubits has been compiled if it has been expressed as a SEO (sequence of elementary operations, like CNOTs and single-qubit operations). SEO's are often represented as quantum circuits. arXiv:quant-ph/0702144 by Farhi-Goldstone-Gutmann has inspired a recent flurry of papers, that propose quantum algorithms for evaluating NAND formulas via quantum walks over tree graphs. These algorithms use two types of unitary evolution: oracle and non-oracle. Non-oracle evolutions are independent of the NAND formula input, whereas oracle evolutions depend on this input. In this paper we compile (i.e., give explicit SEOs and their associated quantum circuits for) the oracle and non-oracle evolution operators used in some of these NAND formula evaluators. We consider here only the case of balanced binary NAND trees. Our compilation methods are based on the CSD (Cosine Sine Decomposition), a matrix decomposition from Linear Algebra. The CS decomposition has been used very successfully in the past to compile unstructured unitary matrices exactly.
A quantum compiler is a software program for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). The author of this paper is also the author of a quantum compiler called Qubiter. Qubiter uses a matrix decomposition called the Cosine-Sine Decomposition (CSD) that is well known in the field of Computational Linear Algebra. One way of measuring the efficiency of a quantum compiler is to measure the number of CNOTs it uses to express an unstructured unitary matrix (a unitary matrix with no special symmetries). We will henceforth refer to this number as εεε. In this paper, we show how to improve εεε for Qubiter so that it matches the current world record for εεε, which is held by another quantum compiling algorithm based on CSD.
An important result from the mid nineties shows that any unitary evolution may be realized as a sequence of controlled-not and one-qubit gates. This work surveys especially efficient circuits in this library, in the special case of evolutions on two-quantum bits. In particular, we show that to construct an arbitrary two-qubit state from |00>, one CNOT gate suffices. To simulate an arbitrary two-qubit operator up to relative phases, two CNOTs suffice. To simulate an arbitrary two-qubit operator up to global phase, three CNOTs suffice. In each case, we construct an explicit circuit and prove optimality in the generic case. We also contribute a procedure to determine the minimal number of CNOT gates necessary to simulate a given two-qubit operator up to global phase. We use this procedure to discuss timing a given Hamiltonian to simulate the CNOT and to determine an optimal circuit for the two-qubit Quantum Fourier Transform. Our constructive proofs amount to circuit synthesis algorithms and have been coded in C++.
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2^n x 2^n unitary matrices into efficient circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates. We first present a general algebraic optimization technique, which we call the Palindrome Transform, that can be used to minimize the number of self-inverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an numerative algorithm for minimal (n-1)-controlled-NOT circuit construction, which we call the Palindromic Optimization Algorithm. Our work dramatically reduces the number of gates generated by the conventional two-level decomposition method for constructing quantum circuits of (n-1)-controlled single-qubit and (n-1)-controlled-NOT gates.