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/9902062

A Rudimentary Quantum Compiler(2cnd Ed.)

Robert R. Tucci

Published Feb 18, 1999• 89 citations
arXivHTMLPDF

Abstract

We present a new algorithm for reducing an arbitrary unitary matrix U into a sequence of elementary operations (operations such as controlled-nots and qubit rotations). Such a sequence of operations can be used to manipulate an array of quantum bits (i.e., a quantum computer). Our algorithm applies recursively a mathematical technique called the CS Decomposition to build a binary tree of matrices whose product, in some order, equals the original matrix U. We show that the Fast Fourier Transform (FFT) algorithm is a special case of our algorithm. We report on a C++ program called "Qubiter" that implements the ideas of this paper. Qubiter(PATENT PENDING) source code is publicly available.

DOI
10.48550/arxiv.quant-ph/9902062

Related papers

A Rudimentary Quantum Compiler

Robert R. Tucci

We present a new algorithm for reducing an arbitrary unitary matrix into a sequence of elementary operations (operations such as controlled-nots and qubit rotations). Such a sequence of operations can be used to manipulate an array of quantum bits (i.e., a quantum computer). We report on a C++ program called "Qubiter" that implements our algorithm. Qubiter source code is publicly available.

arXiv:quant-ph/9805015•May 7, 1998•57 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•8 citations

Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition

Robert R. Tucci

A quantum compiler is a software program for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). Coppersmith showed that the $\nb$-bit Discrete Fourier Transform matrix $U_{FT}$ can be decomposed in a very efficient way, as a sequence of order($\nb^2$) elementary operations. Can a quantum compiler that doesn't know a priori about Coppersmith's decomposition nevertheless decompose $U_{FT}$ as a sequence of order($\nb^2$) elementary operations? In other words, can it rediscover Coppersmith's decomposition by following a much more general algorithm? Yes it can, if that more general algorithm is the recursive application of the Cosine-Sine Decomposition (CSD).

arXiv:quant-ph/0411097•Nov 15, 2004•7 citations

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

How to Compile A Quantum Bayesian Net

Robert R. Tucci

We show how to express the information contained in a Quantum Bayesian (QB) net as a product of unitary matrices. If each of these unitary matrices is expressed as a sequence of elementary operations (operations such as controlled-nots and qubit rotations), then the result is a sequence of operations that can be used to run a quantum computer. QB nets have been run entirely on a classical computer, but one expects them to run faster on a quantum computer.

arXiv:quant-ph/9805016•May 7, 1998•10 citations

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•69 citations
We present a new algorithm for reducing an arbitrary unitary matrix U into a sequence of elementary operations (operations such as controlled-nots and qubit rotations). Such a sequence of operations can be used to manipulate an array of quantum bits (i.e., a quantum computer). Our algorithm applies recursively a mathematical technique called the CS Decomposition to build a binary tree of matrices whose product, in some order, equals the original matrix U. We show that the Fast Fourier Transform (FFT) algorithm is a special case of our algorithm. We report on a C++ program called "Qubiter" that implements the ideas of this paper. Qubiter(PATENT PENDING) source code is publicly available.
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.
A quantum compiler is a software program for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). Coppersmith showed that the $\nb$-bit Discrete Fourier Transform matrix UFTU_{FT}UFT​ can be decomposed in a very efficient way, as a sequence of order($\nb^2$) elementary operations. Can a quantum compiler that doesn't know a priori about Coppersmith's decomposition nevertheless decompose UFTU_{FT}UFT​ as a sequence of order($\nb^2$) elementary operations? In other words, can it rediscover Coppersmith's decomposition by following a much more general algorithm? Yes it can, if that more general algorithm is the recursive application of the Cosine-Sine Decomposition (CSD).
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.