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

Quantum Compiling with Approximation of Multiplexors

Robert R. Tucci

Published Dec 9, 2004• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0412072

Related papers

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

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•48 citations

Simplifying Quantum Circuits via Circuit Invariants and Dressed CNOTs

Robert R. Tucci

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.

arXiv:quant-ph/0606061•Jun 7, 2006•1 citation

Quantum compiling problem without the inverses: an approach that reduces to multi-dimensional Knapsack problem

Yertay Zhiyenbayev, V. M. Akulin, Aikaterini Mandilara

Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision $\varepsilon$. Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter `nets' around the unity comprised by successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision $\varepsilon$ scales as $ \log (1/\varepsilon )^{\log 3 / log 2} $ while the pre-compilation time is increased as compared to thatof the Solovay-Kitaev algorithm by the exponential factor 3/2.

•Aug 29, 2017•0 citations

An Optimization for Qubiter

Robert R. Tucci

In a previous paper, we described a computer program called Qubiter which can decompose an arbitrary unitary matrix into elementary operations of the type used in quantum computation. In this paper, we describe a method of reducing the number of elementary operations in such decompositions.

arXiv:quant-ph/9809055•Sep 17, 1998•0 citations

A Rudimentary Quantum Compiler(2cnd Ed.)

Robert R. Tucci

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.

arXiv:quant-ph/9902062•Feb 18, 1999•30 citations
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\nb\nb-bit unstructured unitary matrix (a unitary matrix with no special symmetries) that we wish to compile. For \nb>10\nb>10\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.
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.
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.
Given a set of quantum gates and a target unitary operation, the most elementary task of quantum compiling is the identification of a sequence of the gates that approximates the target unitary to a determined precision ε\varepsilonε. Solovay-Kitaev theorem provides an elegant solution which is based on the construction of successively tighter `nets' around the unity comprised by successively longer sequences of gates. The procedure for the construction of the nets, according to this theorem, requires accessibility to the inverse of the gates as well. In this work, we propose a method for constructing nets around unity without this requirement. The algorithmic procedure is applicable to sets of gates which are diffusive enough, in the sense that sequences of moderate length cover the space of unitary matrices in a uniform way. We prove that the number of gates sufficient for reaching a precision ε\varepsilonε scales as $ \log (1/\varepsilon )^{\log 3 / log 2} $ while the pre-compilation time is increased as compared to thatof the Solovay-Kitaev algorithm by the exponential factor 3/2.
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.