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

Canadian Journal of Physics

Householder methods for quantum circuit design

Jesús Urı́as, Diego Quiñones

Published Oct 28, 2015• 5 citations
Publisher

Abstract

Algorithms to resolve multiple-qubit unitary transformations into a sequence of simple operations on one-qubit subsystems are central to the methods of quantum-circuit simulators. We adapt Householder’s theorem to the tensor-product character of multi-qubit state vectors and translate it to a combinatorial procedure to assemble cascades of quantum gates that recreate any unitary operation U acting on n-qubit systems. U may be recreated by any cascade from a set of combinatorial options that, in number, are not lesser than super-factorial of 2n, [Formula: see text]. Cascades are assembled with one-qubit controlled-gates of a single type. We complement the assembly procedure with a new algorithm to generate Gray codes that reduce the combinatorial options to cascades with the least number of CNOT gates. The combined procedure —factorization, gate assembling, and Gray ordering — is illustrated on an array of three qubits.

DOI
10.1139/cjp-2015-0490

Related papers

The Design and Optimization of Quantum Circuits using the Palindrome Transform

Krysta M. Svore, Alfred V. Aho

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n 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 selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative 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.

•Sep 1, 2003•5 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•335 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

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

Describing Quantum Circuits with Systolic Arrays

Aasavari Bhave, Eurı́pides Montagne, Edgar Granados

In the simulation of quantum circuits the matrices and vectors used to represent unitary operations and qubit states grow exponentially as the number of qubits increase. For instance, the evolution of an n-qubit quantum system in an initial superposition state is described by a 2n x 2n unitary matrix. However, the evolution of an n-qubit quantum system can be described as well as a composition of single-qubit and controlled-not unitary operations which are equivalent to the 2n x 2n unitary matrix. A strategy is suggested for the mapping of onequibit and two-qubit gates onto a three PE systolic array, and then we show how the interconnection of those systolic arrays can be used to implement or describe quantum circuits. As a case study we present the description of the teleportation algorithm.

IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP)•Jan 1, 2006•0 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and Education•Sep 30, 2020•4 citations
Algorithms to resolve multiple-qubit unitary transformations into a sequence of simple operations on one-qubit subsystems are central to the methods of quantum-circuit simulators. We adapt Householder’s theorem to the tensor-product character of multi-qubit state vectors and translate it to a combinatorial procedure to assemble cascades of quantum gates that recreate any unitary operation U acting on n-qubit systems. U may be recreated by any cascade from a set of combinatorial options that, in number, are not lesser than super-factorial of 2n, [Formula: see text]. Cascades are assembled with one-qubit controlled-gates of a single type. We complement the assembly procedure with a new algorithm to generate Gray codes that reduce the combinatorial options to cascades with the least number of CNOT gates. The combined procedure —factorization, gate assembling, and Gray ordering — is illustrated on an array of three qubits.
The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2n×2n 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 selfinverting gates in quantum circuits consisting of concatenations of palindromic subcircuits. For a fixed column ordering of two-level decomposition, we then give an enumerative 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.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
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.
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++.
In the simulation of quantum circuits the matrices and vectors used to represent unitary operations and qubit states grow exponentially as the number of qubits increase. For instance, the evolution of an n-qubit quantum system in an initial superposition state is described by a 2n x 2n unitary matrix. However, the evolution of an n-qubit quantum system can be described as well as a composition of single-qubit and controlled-not unitary operations which are equivalent to the 2n x 2n unitary matrix. A strategy is suggested for the mapping of onequibit and two-qubit gates onto a three PE systolic array, and then we show how the interconnection of those systolic arrays can be used to implement or describe quantum circuits. As a case study we present the description of the teleportation algorithm.
Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.