PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Circuits for Isometries

Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, Matthias Christandl

arXiv:1501.06911v4quant-ph

TL;DR

The paper asks how to decompose arbitrary isometries while limiting costly C-not gates. It derives a theoretical lower bound and presents three decompositions, with the best schemes approaching that bound within roughly a factor of two in leading order.

  • Problem

    C-not gates are often difficult to implement, so the paper studies how to decompose arbitrary m-to-n isometries while minimizing their number.

  • Method

    The paper derives a parameter-counting lower bound and constructs three isometry decompositions, including a column-by-column scheme and a unitary-based adaptation.

  • Results

    The worst-case decomposition uses roughly 2.3 times the lower-bound C-not count for sufficiently large n.

  • Takeaways & Limitations

    The schemes provide C-not-efficient constructions for arbitrary isometries, including optimized cases with m to n ≤ 4.

Abstract

from arXiv · show

We consider the decomposition of arbitrary isometries into a sequence of single-qubit and Controlled-NOT (C-NOT) gates. In many experimental architectures, the C-NOT gate is relatively 'expensive' and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of C-NOT gates required to decompose an arbitrary isometry from m to n qubits, and give three explicit gate decompositions that achieve this bound up to a factor of about two in the leading order. We also perform some bespoke optimizations for certain cases where m and n are small. In addition, we show how to apply our result for isometries to give decomposition schemes for arbitrary quantum operations and POVMs via Stinespring's theorem. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.

I. INTRODUCTION

The paper targets C-not-efficient decompositions of arbitrary isometries because C-not gates are often difficult to implement. It derives lower bounds, proposes three schemes, and optimizes small cases.

  • Motivation: C-not gates are often the most difficult operations to perform in the chosen universal gate library, motivating circuits that minimize their number.The library uses arbitrary single-qubit operations and C-not gates.
  • Problem setting: An isometry maps between Hilbert spaces of potentially different dimensions and includes state preparation and arbitrary unitaries as special cases.Its extra freedom relative to a general unitary can reduce the required C-not count.
  • Decomposition schemes: 2 · 2^m+n C-nots is reduced to 2^m+n + 2^n to leading order in the first decomposition scheme.The original construction used Knill’s scheme together with state preparation as a black box.
  • Decomposition schemes: The second scheme uses a column-by-column decomposition requiring about 2^m+n C-not gates, while the third uses about 0.16 · (4^m + 2 · 4^n).The column-by-column scheme also performs well when m and n are small.
  • Bounds and optimization: 2.3 times the lower-bound C-not count is used in the worst case for sufficiently large n, comparable to the known factor of 1.9 for state preparation and arbitrary unitaries.The worst case is an n−2 to n isometry.
  • Bounds and optimization: m to n isometries with n ≤ 4 receive bespoke C-not optimizations because these cases are expected to matter for near-future experiments.The optimized counts are summarized in Table III.
  • Gate-count implications: The C-not counts also upper-bound total gate counts, since each C-not can introduce at most two nonredundant single-qubit gates, plus n additional gates.This gives a direct estimate for the full circuit size.
  • Caveat: Decomposition rankings by gate count can depend on the physical setup, and improving a black-box subroutine can change the ordering.Knill’s construction, for example, uses state preparation as a black box.

II. BACKGROUND INFORMATION AND NOTATION

The paper fixes circuit-model notation for qubits, gates, rotations, and circuit topologies, while tabulating C-not counts for competing isometry decompositions and small cases.

  • Circuit notation: Quantum circuits represent qubits as wires and gates as operations, with time conventionally flowing from left to right.Computational basis states are represented by bit strings in the 2^n-dimensional Hilbert space.
  • Gate notation: Arbitrary single-qubit gates are counted directly, rather than restricting gates to rotations about a fixed axis.The paper uses rotations about the x, y, and z axes.
  • Count tables: Table II compares C-not requirements across decomposition schemes, including column-by-column and Cosine-Sine constructions.Small-n cases receive additional optimizations summarized separately in Table III.
  • Count tables: For 2 ≤ n ≤ 4, Table III reports the smallest known achievable C-not counts, including special state-preparation entries and remaining cases discussed in Appendix B.The table notes that counts grow very rapidly, reaching about 500000 C-nots for a 10-qubit unitary.
  • Gate notation: A C-not is a control-conditioned σx operation, with σx expressed as a π rotation about the x axis.The displayed form applies σx when the control is |1⟩.
  • Gate notation: Every single-qubit unitary admits a ZYZ decomposition with three real parameters after ignoring global phase.The parameters correspond to Euler-angle-like rotations.
  • Circuit notation: Circuit-topology equivalence means that every parameter setting on one topology can be matched on another to implement the same operation up to global phase.Free symbols represent gates with unspecified parameters.

III. LOWER BOUND

The lower-bound argument compares the real parameters needed to specify an arbitrary m-to-n isometry with those supplied by single-qubit gates and C-nots.

  • Parameter counting: An m-to-n isometry is a 2^n × 2^m complex matrix satisfying V†V = I, and its parameter count sets the target for a universal circuit topology.The isometry is described by 2^(n+m+1) − 2^(2m) − 1 real parameters.
  • Parameter counting: Without C-nots, single-qubit unitaries supply at most 3 parameters on input qubits and 2 on qubits initialized to |0⟩.Additional parameters therefore require entangling gates.
  • Parameter counting: Each additional C-not contributes at most four real parameters, rather than six, because certain rotations commute with the control or target.The relevant commutation relations are Rz with controls and Rx with targets.
  • Lower bound: 3m + 2(n − m) + 4r is the maximum number of real parameters introduced using r C-nots.This combines the single-qubit and C-not contributions.
  • Lower bound: The lower bound follows by requiring 3m + 2(n − m) + 4Niso(m,n) to meet or exceed the isometry’s parameter count.This condition is necessary for a topology to generate every m-to-n isometry.
  • Scope: Almost every m-to-n isometry requires at least the derived ceiling-valued number of C-nots in circuits using single-qubit unitaries and C-nots.The statement excludes a measure-zero set of isometries.
  • Scope: The excluded measure-zero set contains interesting operations such as the isometry required for Shor’s algorithm, so the bound limits universal rather than task-tailored computers.Additional ancilla qubits do not affect the lower bound.

IV. DECOMPOSITION SCHEMES FOR ISOMETRIES

The paper embeds an isometry into a larger unitary and gives three constructive decompositions for that unitary using single-qubit gates and C-nots.

  • Unitary representation: An m-to-n isometry V can be represented by a 2^n × 2^n unitary U whose first 2^m columns equal V.The representing unitary is not unique unless m = n.
  • Unitary representation: The decomposition problem is therefore to implement a suitable unitary extension U with C-nots and single-qubit gates.The freedom in choosing U supports constructive isometry decompositions.
  • Constructive schemes: The paper presents three constructive decomposition schemes and describes their main ideas in the section, with full technical details deferred to Appendix A.The schemes also provide alternative universality proofs for the single-qubit-and-C-not gate library.

A. Notation for controlled gates

The paper defines uniformly controlled gates by assigning different target unitaries to control-qubit states, and distinguishes them from multi-controlled gates with only one nonidentity control branch.

  • Uniformly controlled gates: A uniformly controlled gate applies a different l-qubit unitary for each of the 2^k states of k control qubits.The notation uses U as a placeholder for the set of target unitaries.
  • Uniformly controlled gates: The n-qubit Hilbert space is split into control, target, and free-qubit subsystems with dimensions 2^k, 2^l, and 2^f.Here f = n − l − k, and free qubits are neither controlled nor acted upon.
  • Multi-controlled gates: A multi-controlled gate is obtained when all but one of the control-conditioned target unitaries are identities.For l = 1, the notation emphasizes the total number of qubits involved.
  • Notation conventions: The notation C_k(U) leaves the control and target qubits, and whether control is on |0⟩ or |1⟩, unspecified until the context defines them.Control-on-zero and control-on-one versions use the same C-not count because X gates can switch the control convention.
  • Decomposition and notation: A uniformly k-controlled gate decomposes into 2^k k-controlled gates.The paper illustrates this structure for k = 2 and l = n − 2.

B. Decomposition of isometries using the decomposition scheme of Knill

This scheme combines Knill’s isometry decomposition with state-preparation circuits, merging unitary factors and decomposing controlled phase gates to obtain an explicit C-not construction.

  • Construction: The first scheme combines Knill’s isometry decomposition with the paper’s state-preparation decomposition.The construction is presented as a main theorem for isometries with n ≥ 5.
  • Construction: The leading-order cost is expressed using NU(n), the C-not count for an arbitrary n-qubit unitary, together with state-preparation and lower-order terms.For large n, the last three terms are negligible, so the leading order derives from a unitary on ⌊n/2⌋ qubits.
  • Gate count: The resulting count is approximately 2^m+n + 2^n to leading order for the first decomposition scheme.The displayed expression separates the dominant isometry term from the state-preparation contribution.
  • Construction: The construction decomposes each Vi by reversing a state-preparation scheme and uses 2^m − 1 instances of the resulting circuit pattern.Here Vi is a unitary that prepares the state corresponding to the ith column of V.
  • Circuit simplification: Merging adjacent unitary factors reduces the circuit description before the remaining controlled phase gates are decomposed.The paper defines merged factors ˜U1 := U3U1 and ˜U2 := U4U2.
  • Gate count: 16n^2 − 60n + 42 C-nots suffice for each relevant (n−1)-controlled phase gate, yielding the stated count.These phase gates are special cases of controlled-U gates and are decomposed using the paper’s controlled-gate lemma.

C. Column-by-column decomposition

The column-by-column scheme constructs successive unitaries that map each isometry column to a computational-basis vector while preserving earlier columns, producing explicit C-not bounds and revealing inefficiency near square isometries.

  • Column-by-column construction: A column-by-column decomposition constructs Gk so that the next column maps to |k⟩n while earlier computational-basis columns remain fixed.The product G2^m−1⋯G0 then satisfies GV = I2n×2m.
  • Gate-count analysis: Theorem 2 gives an explicit C-not upper bound for arbitrary m-to-n isometries, obtained from the per-column cost Ncol and an additional diagonal contribution.The total bound is written as 2^mNcol + NΔ(m).
  • First column: G0 is obtained by reversing state preparation on V|0⟩m, and successive uniformly controlled gates disentangle the qubits one at a time.For the first column, the gates successively zero entries until the state is reduced to a basis state.
  • Later columns: For the second column, modified controlled gates avoid disturbing |0⟩n by excluding the upper block and correcting it with an additional multi-controlled gate.The construction sets the second column while preserving the first column.
  • Gate-count analysis: The construction uses uniformly controlled gates up to diagonal factors, then combines those decompositions with diagonal-gate and controlled-gate counts.The proof is constructive, and the exact C-not count is given in equation (A21).
  • Scope and optimization: Because each column costs about 2^n C-nots to leading order, the column-by-column scheme is inefficient when m is close to n.The paper introduces a CSD-based scheme for m = n − 1 and m = n, with the m = n case matching the unitary decomposition scheme.
  • Nearest-neighbour implementation: The scheme uses at most (5/3)2^m+n + O(n) nearest-neighbour C-not gates when the uniformly controlled gates are implemented efficiently.This is a topology-specific bound for nearest-neighbour architectures.

D. Decomposition of isometries using the Cosine-Sine Decomposition

The CSD approach adapts recursive unitary decomposition to m-to-n isometries, but can zero more matrix entries than necessary when m<n−1. Its resulting C-not count is improved by an optimized state-preparation construction.

  • CSD construction: The CSD approach adapts recursive decomposition of arbitrary unitaries into single-qubit gates and uniformly controlled Ry and Rz gates for m-to-n isometries.An isometry is represented using a unitary V_n satisfying V = V_n I_{2^n×2^m}.
  • CSD construction: N_iso(m, n) ⩽ 3 · 2^(2n−3) − 2^n + 2^(m−4)(3 · 2^m − 8) C-nots for the stated construction.The bound is given for arbitrary m-to-n isometries with 2 ≤ m ≤ n.
  • Recursive implementation: The recursive construction decomposes uniformly (n−1)-controlled rotations with at most 2^(n−1) C-nots and recursively decomposes the remaining unitaries.The recursion continues until two-qubit gates remain, each implementable with 3 C-nots.
  • CSD limitation: For m<n−1, CSD zeroes unnecessary entries in matrix blocks, causing more C-not gates than needed as m decreases.The number of unnecessary zeros grows as m decreases.
  • State preparation: For large odd n, the state-preparation circuit has C-not depth 3/4 · 2^(2n) to leading order, improving the previous bound.The cited passage reports the preceding and improved leading-order depth bounds, although the extracted numerical expressions are incomplete.

V. COMPARISON OF DECOMPOSITIONS

The paper compares optimized Knill, column-by-column, and CSD decompositions by their ratios to the isometry lower bound. Performance depends on m and n, while small cases receive separate optimizations.

  • Comparison framework: The comparison uses ratios cK(m, n), cCC(m, n), and cCSD(m, n) between each decomposition’s C-not count and the lower bound.The ratios correspond to optimized Knill, column-by-column, and CSD decompositions, respectively.
  • Asymptotic comparison: For m≤4 and large n, column-by-column decomposition requires fewer C-nots, with cCC(m, n) ≃2 while optimized Knill ranges up to cK(0, n) ≃4.8 for odd n.For m≥5 and large n, optimized Knill and column-by-column perform similarly.
  • Asymptotic comparison: For m=n−1 and large n, CSD reaches cCSD(n−1, n) ≃1.9, while column-by-column gives cCC(n−2, n) ≃2.3 and cCC(n−1, n) ≃2.7.The CSD approach may outperform the other decompositions when m is close to n.
  • Small instances: The column-by-column and CSD approaches also perform well for small isometries with m to n≤4, summarized in Table III.The paper provides a step-by-step decomposition for these cases in Appendix B.
  • Architectural trade-offs: The column-by-column scheme adapts well to nearest-neighbour C-not constraints, whereas optimized Knill permits parallel execution of some gates.These architectural differences can matter beyond total gate counts.
  • Architectural trade-offs: Improving the decomposition of building blocks can improve the leading-order C-not count of the resulting isometry decomposition.The dependence differs between column-by-column and optimized Knill schemes.

VI. APPLICATION TO QUANTUM OPERATIONS AND POVMS

The paper extends isometry decompositions to quantum channels and POVMs using Stinespring’s and Naimark’s theorems. It also derives a circuit-topology lower bound for arbitrary CPTP maps.

  • Quantum channels: Any CPTP map can be implemented by an isometry followed by partial trace, allowing isometry decompositions to synthesize arbitrary quantum channels.This application uses Stinespring’s theorem.
  • Lower-bound setting: The lower-bound analysis permits k qubits with single-qubit and C-not gates, followed by tracing out k−n qubits.Tracing out can be deferred to the end because it commutes with gates on the retained system.
  • Lower bound: A circuit topology implementing arbitrary CPTP maps from m to n qubits requires at least the stated lower-bound number of C-nots.The bound follows from counting the real parameters needed to specify CPTP maps.
  • Quantum channels: Stinespring’s theorem represents a channel using an isometry from A to BC, where C contains at most n+m qubits, followed by partial trace on C.The paper applies a column-by-column decomposition to this isometry.
  • Quantum channels: The resulting constructive and exact channel implementation uses about four times the C-not lower bound for sufficiently large n.The stated count is obtained without exploiting unitary freedom on C.
  • Scope: The channel results are restricted to the quantum circuit model; future work considers measurements or classical randomness as additional resources.Alternative channel implementations may permit further C-not reductions.
  • POVMs: By Naimark’s theorem, arbitrary POVMs can be implemented by an isometry into an enlarged system followed by measurement, so isometry schemes apply to POVMs.The enlargement is from system A to AB, with measurement on B.

1. Decomposition of MCGs

The MCG construction targets efficient decompositions of multi-controlled gates, especially controlled single-qubit unitaries and X gates. Recursive identities, diagonal-gate cancellation, and Toffoli decompositions yield explicit C-not bounds.

  • Target gates: The construction focuses on C_{n−1,n}(W) gates with W∈SU(2), using technical optimizations to reduce their C-not counts.Control-on-zero versions have the same count as control-on-one versions after conjugation by two σ_x gates.
  • Toffoli optimization: Toffoli gates can be implemented with 6 C-nots, and their count can be halved when implementation is required only up to a diagonal gate.Diagonal gates commute with uniformly controlled gates, enabling cancellations in the optimized constructions.
  • Controlled X gates: A k-controlled X gate C_{k,n}(σ_x) can be implemented with at most 8k−6 C-nots for n≥5 and k≤⌈n/2⌉.The k=1 case is trivial, while k=2 follows from a Toffoli construction.
  • Construction mechanism: The MCG decompositions use recursive action and reset parts, with diagonal-gate cancellations reducing the cost of controlled X subcircuits.For the analyzed reset construction, the count is expressed as 4(k−3)+3 C-nots.
  • Summary of building blocks: Table IV summarizes C-not counts and the numbers of real parameters introduced by several uniformly and non-uniformly controlled gates.Controlled gates are treated as circuit building blocks for larger decompositions.
  • Controlled X gates: A C_{n−2,n}(σ_x) gate decomposes into two C_{k,n}(σ_x) and two C_{n−k−1,n}(σ_x) gates.The identity holds for k∈{2,3,…,n−3}.
  • General controlled unitaries: A C_{n−1,n}(U) gate requires at most 16n^2−60n+42 C-nots for n≥3.This bound applies to an arbitrary single-qubit unitary U.
  • Specialized SU(2) bound: For W∈SU(2) and n≥8, C_{n−1,n}(W) requires at most 28n−88 C-nots for even n and 28n−92 for odd n.The specialized SU(2) construction improves the general controlled-unitary bound.

3. Rigorous proof of the decomposition scheme described in Section IV C and exact C-not count

The column-by-column construction recursively disentangles one qubit at a time while preserving earlier basis states up to phases, yielding an explicit C-not count and a near-lower-bound asymptotic scheme.

  • Recursive construction: Binary digits of k determine which controlled gates are applied during the recursive disentangling procedure.The construction uses k_s and neighboring higher-order bits to select multi-controlled gates.
  • Recursive construction: The gate G_k preserves the first k basis states up to phase factors while transforming the remaining state as required.Its circuit uses uniformly controlled gates, diagonal gates, and selected multi-controlled gates whose controls can commute by construction.
  • Exact counting: A single-column decomposition uses at most (2^n − n − 1) plus Q_k(n) times the C-not cost of an (n−1)-controlled gate.Here Q_k(n) counts the relevant positions s where k_s=0 and b_{s+1} is nonzero.
  • Exact counting: The resulting column-by-column scheme requires about 2^m+n C-not gates to leading order and performs well when m and n are small.The paper compares this construction with an explicit lower bound for arbitrary isometries.

4. Optimization of the decomposition of an isometry using the CSD

The optimized CSD approach adapts unitary decompositions to isometries and combines neighboring controlled rotations to reduce C-not usage, while also enabling recursive state-preparation constructions.

  • CSD optimization: The optimized CSD decomposition adapts the decomposition of arbitrary unitaries to isometries and saves one C-not for each uniformly controlled Ry gate.The optimization combines controlled-Ry gates with neighboring uniformly controlled gates rather than decomposing them independently.
  • CSD optimization: The optimized count is obtained by stopping the CSD recursion at two-qubit unitaries and saving one C-not for nearly every remaining two-qubit gate.The number of such gates is tracked by a recursion for QU2(m,i).
  • State preparation: State preparation recursively divides qubits into two groups, reducing the problem to smaller state-preparation instances, C-nots, and two smaller unitary operations.For odd n, the construction replaces one unitary with an isometry of adjacent dimensions.
  • State preparation: The circuit depth is, to leading order, determined by the steps implementing U2 because U1 and U2 can run in parallel and U2 dominates the gate count.This depth statement concerns the recursive state-preparation circuit.
  • Small cases: A 1-to-2 isometry admits an ad hoc decomposition reaching the theoretical lower bound of two C-not gates.The construction exploits that only the first two columns of an embedded two-qubit unitary matter.

a. Isometries from one to three qubits

Small isometries receive specialized constructions that exploit trivial action on unused input states, optimized controls, and state-preparation subroutines.

  • Isometries from one to three qubits: The 1-to-3 construction uses a column-by-column decomposition, implementing UCGs together with diagonal gates and treating the first column as three-qubit state preparation.The second column is constructed so the circuit acts trivially on the all-zero input state.
  • Isometries from one to three qubits: Switching UCG and MCG order and omitting some MCG controls simplifies the small 1-to-3 circuit because the relevant gates commute by construction.The same type of simplification can apply to many MCGs in larger column-by-column decompositions.
  • Isometries from two to three qubits: For two-to-three isometries, the CSD approach embeds the isometry into an 8×8 unitary and simplifies the decomposition using the known initial |0⟩ state.The first block can always be applied to the last two qubits at the start of the circuit.
  • Isometries from one to four qubits: For one-to-four isometries, state preparation supplies the first column with 8 C-nots, while the optimized second-column construction uses 22 C-nots.The latter implements MCGs through UCGs up to diagonal gates and corrects the diagonal contribution on the least significant qubit.
  • Isometries from one to four qubits: The one-to-four construction acts trivially on |0000⟩, and the circuit notation uses arbitrary complex entries for unconstrained amplitudes.These conventions describe the optimized controlling of the MCGs in the second-column circuit.
Loading 1501.06911v4…