Source-linked AI summary
A Quantum Circuit for Gaussian Elimination
Hochang Lee, Kyung Chul Jeong, Panjin Kim
TL;DR
Earlier quantum Gaussian-elimination circuits were restricted to GF(2), and reversible implementation must address the mapping's non-injectivity. This paper develops a circuit for any finite field using a pseudo row echelon form; in GF(2), it improves on previous work in either Toffoli depth or qubit count.
Problem
Prior quantum circuits covered only GF(2), and either did not attain minimum garbage space or did not match classical complexity.
Source: §1 · p. 1Method
The circuit uses a pseudo row echelon form to make Gaussian elimination reversible while retaining the information needed to reverse the operation.
Source: §1 · p. 1Results
In GF(2), the circuit improves on previous works either in Toffoli depth or number of qubits.
Source: §1 · p. 2Takeaways & Limitations
The design generalizes quantum Gaussian elimination to any finite field, beyond the GF(2) setting of prior circuits.
Source: §5 · p. 14Further optimization remains possible, including shortening multiplication depth before realistic-hardware implementation.
Source: §5 · p. 14
Abstract
from arXiv · showhide
A quantum circuit for Gaussian elimination is developed in this work. While previous quantum implementations of Gaussian elimination were restricted to $\mathrm{GF}(2)$, the proposed design is generalized to any finite field. Compared with previous works in $\mathrm{GF}(2)$, the developed circuit achieves garbage-free construction while retaining the best known asymptotic Toffoli depth up to logarithmic factors.
1 Introduction
The paper extends quantum Gaussian elimination beyond GF(2) and addresses the non-injective mapping's garbage-space cost. Its construction uses a pseudo row echelon form and, in GF(2), improves on prior circuits in either Toffoli depth or qubit count.
1 Introduction
- Earlier quantum circuits covered only GF(2) and either failed to attain minimum garbage space or failed to match classical complexity.The mapping is non-injective, so reversible implementation requires at least x−y workspace bits when the input and output have x and y bits.Source: §1 · p. 1
- The work generalizes quantum Gaussian elimination to any finite field, whereas its prior quantum implementations were restricted to GF(2).The introduction frames low-level reversible implementation as a way to estimate quantum algorithm performance.Source: §1 · p. 1
- The pseudo row echelon form makes the non-injective elimination mapping one-to-one while preserving the row-echelon information needed to solve linear systems.The construction uses no garbage space beyond the input qubits: the result overwrites the input, while the minimum reversal information is retained.Source: §1 · p. 1
- In GF(2), the developed circuit improves on previous works either in Toffoli depth or number of qubits.Table 1 summarizes circuit complexities, temporary workspace, and supplemental garbage space for GF(2) matrices.Source: §1 · p. 2, Table 1 · p. 2
2 Preliminaries
The preliminaries define Gaussian elimination and its reversible-circuit setting, introduce notation and pseudo row echelon form, specify cost measures, and review prior GF(2) circuits.
2.1 Gaussian Elimination
- Gaussian elimination uses row operations to reach row echelon form; conditional operations complicate quantum implementation, though the design aims to retain classical complexity.The classical arithmetic complexity is O(n^2m), for m rows and n columns.Source: §2.1 · pp. 2–3
2.2 Notation and Definition
- Pseudo row echelon form preserves the upper-triangular entries of the row echelon form, while information in its unspecified lower and diagonal parts supports reversibility.It can solve linear systems as row echelon form does; rank-deficient matrices are possible but substantially complicate the construction.Source: §2.2 · pp. 3–4
- The pivot index is the first nonzero entry in the first column, and the paper also defines submatrix notation and finite-field division for the additive identity.The setting is GF(p^l), with p prime and l positive.Source: §2.2 · pp. 3–4
2.3 Cost Measure
- Toffoli gates alone determine gate cost; depth counts non-parallelizable operations, and space is measured by qubit count.Lower-level decomposition of Toffoli gates is outside the work's scope.Source: §2.3 · p. 4
2.4 Previous works
- Earlier quantum Gaussian-elimination circuits addressed GF(2); the paper compares them there while its circuit applies to any finite field.The prior work includes circuits for syndrome decoding and symmetric-key primitives; one design can be modified to use at most m−1 temporary work qubits while retaining asymptotic gate and depth complexities.Source: §2.4 · pp. 4–5
3 Algorithm
The section presents a reversible algorithm for producing a pseudo row echelon form through pivot selection, row operations, and pivot-index deletion. It gives quantum-cost bounds for the algorithm and a separate Toffoli bound for GF(2).
3 Algorithm
- Algorithm 1 processes each column by finding a pivot, swapping its row to the top, reducing rows, and deleting the pivot index.The section specifies that the algorithm outputs a pseudo row echelon form.Source: §3 · pp. 5–6
- RowReduction normalizes row entries relative to the leading entry and subtracts the first row from other rows, excluding the first column.The algorithm handles field arithmetic whose implementation can affect the circuit's Toffoli depth.Source: §3 · pp. 5–6
- For m ≥ n, Algorithm 1 is reversibly implementable with its quantum cost summarized in Table 3.The stated condition m ≥ n reflects the paper's focus on full-rank matrices.Source: §3 · p. 6, Table 3 · p. 6
- For GF(2), Algorithm 1 has Toffoli count O(mn^2) and depth O(m log2 n + n(log2 m)^4).The paper notes that arithmetic operations simplify in GF(2).Source: §3 · p. 6
4 Implementations
The implementation section develops reversible subroutines for labeling, pivoting, row reduction, and deleting pivot indices. It then combines their costs across iterations, with borrowed qubits used in the pivoting and row-reduction bounds.
4.1 Labeling
- Labeling encodes the selected pivot row in unary form, using tests of leading entries and index qubits to identify the pivot.A recursive construction parallelizes the labeling process; the serial Toffoli depth is m − 1.Source: §4.1 · pp. 7–9
4.2 Pivoting
- Pivoting uses staged row swaps to move the pivot row to the top, with the output's leading entry nonzero for a full-rank matrix.With α(m − j′)j′ borrowed qubits, its Toffoli count is bounded by 2(α(n − j′) + 1)(m − j′ − 1), and its depth by 2(n − j′)j′ + 3⌈log2(m − j′)⌉.Source: §4.2 · pp. 9–10
4.3 Row reduction
- RowReduction has two phases: normalize each row using its leading entry, then conditionally subtract the first row from other rows outside the first column.These steps involve multiplication, addition, and inverse operations over the field.Source: §4.3 · p. 11
4.4 Deleting the pivot index
- Deleting the pivot index restores work space by partially reversing Pivoting on the first column and fully reversing Labeling.The paper states that this does not change asymptotic complexity and only slightly affects exact complexity because Pivoting is partially reversed.Source: §4.4 · pp. 11–12
4.5 Complexity
- Across n iterations, the complexity analysis aggregates the costs of Labeling, Pivoting, RowReduction, and pivot-index deletion.Borrowed qubits are available for Pivoting and RowReduction because already-processed rows or columns do not participate in those steps.Source: §4.5 · pp. 12–13
5 Discussions
The design generalizes quantum Gaussian elimination from GF(2) to any finite field, while its GF(2) comparison targets classical complexity with limited extra space. Borrowed qubits provide temporary workspace for parallel operations and are restored afterward.
5 Discussions
- The circuit works over any finite field, and the authors report matching classical complexity while limiting extra space in comparisons with prior GF(2) designs.They note that the earlier designs have different strengths and weaknesses in time and space.Source: §5 · p. 14
A Parallelization with borrowed qubits
- Borrowed qubits temporarily carry shared control or input information so overlapping operations can run in parallel, then are corrected and restored to their initial values.The method is applied to controlled swaps in Pivoting and arithmetic operations in RowReduction.Source: A Parallelization with borrowed qubits · p. 17
A.1 Transferring of the shared value to borrowed qubits
- Figure 4 contrasts CNOT-based and addition-based transfer of a shared value to clean or borrowed auxiliary qubits.For borrowed qubits, the illustrated initial values are g1 through g5.Source: Figure 4 · p. 17
A.2 Parallelization of controlled swap operations for Pivoting
Controlled swaps sharing a control can be parallelized by temporarily transferring that control to borrowed qubits, with correction steps preserving the intended operation.
A.2 Parallelization of controlled swap operations for Pivoting
- The control value is copied to a borrowed qubit for parallel use, and an extra controlled swap corrects for its initially unknown value.The transfer and its uncomputation use two CNOT gates.Source: §A.2 · p. 18
- The transfer and uncomputation steps have CNOT count bounded by 4g and CNOT depth bounded by 4 ⌈log2(g + 1)⌉.These bounds are stated for g borrowed qubits.Source: §A.2 · p. 18
- Four controlled swaps sharing one control qubit have controlled-swap depth 2 in the illustrated parallelized circuit.Figure 5 gives the example outcome.Source: Figure 5 · p. 18
A.3 Parallelization of Arithmetic Operations for RowReduction
RowReduction has a multiplication phase and a controlled-addition phase, with repeated shared operands or controls creating opportunities for parallelization using borrowed qubits.
A.3 Parallelization of Arithmetic Operations for RowReduction
- RowReduction's first phase contains quantum–quantum multiplications sharing an input, while its second phase contains controlled quantum–quantum additions sharing an input or control.The target operations are expressed as t + vτ.Source: §A.3 · p. 18
B Details on subroutines
- Figure 6 shows borrowed-qubit parallel implementations for first-phase multiplication and second-phase controlled addition, including overlapping-column and overlapping-row cases.The appendix introduces procedure details and complexities, and notes that w is omitted from Algorithm 1 for notational simplicity.Source: Figure 6 · p. 19, B Details on subroutines · p. 22
A.3 Parallelization of Arithmetic Operations for RowReduction
- The non-zeroness work qubit is referenced n −1 times, and the first row is subtracted from the other rows m −1 times, defining row- and column-direction parallelization opportunities.Sharing the work-qubit workload can reduce depth; parallelizing the first row can also reduce depth.Source: First Phase: Parallelization of… · p. 20
- For shared addends, the column-direction construction transfers the addend to borrowed qubits and adds a correction operation because those qubits may begin with unknown values.Parallelizing one controlled addition requires two controlled additions and two quantum–quantum additions for transfer and uncomputation.Source: First Phase: Parallelization of… · p. 20
- For shared controls, the row-direction construction transfers the control to borrowed qubits and uses controlled additive inversions to correct for their initially unknown values.The stated construction uses two controlled additions, two controlled additive inversions, and two CNOT gates for copying and uncomputing.Source: First Phase: Parallelization of… · p. 21
B.1 Labeling
Labeling encodes the pivot-row index in unary form and can be parallelized by dividing the search across smaller labeling circuits.
B.1 Labeling
- Labeling encodes the index of the pivot row to move to the top row in unary form, and may return −1 when there is no nonzero pivot row.The procedure scans the first column for a nonzero pivot.Source: §B.1 · p. 22
- The labeling circuit can use m −1 qubits rather than m because a control for the first row is unnecessary and the first unary bit is unused.A zero unary value represents selection of the first row.Source: §B.1 · p. 22, Figure 8 · p. 23
- ParallelLabeling divides the candidate rows into two subsets and computes the second subset conditionally on whether the first subset contains a nonzero entry.The parallel construction is based on halving the circuit into smaller labeling circuits.Source: Parallelization · p. 23
- The recursive ParallelLabeling procedure combines results from the two subranges to return the pivot index.Its stated inputs include a control bit, an offset, and a vector of field elements.Source: Parallelization · p. 23
B.2 Pivoting
Pivoting moves the pivot row to the top using label-controlled row swaps, which can be parallelized with borrowed qubits. The section compares pivoting strategies and analyzes the parallel procedure’s costs.
SerialPivoting
- SerialPivoting uses a tournament-like structure to parallelize eligible swaps, with CNOTs transferring label information alongside the selected row.The procedure performs m−1 row swaps in total.Source: §B.2 · p. 24
Complexity and comparison
- Over GF(2), the proposed pivoting uses n(m−1) controlled swaps with depth n⌈log2 m⌉; [9] has depth O(nm(log2 m)3), while has depth m−1+max(n−1, m−1).The [9] approach has Toffoli count O(nm2(log2 m)2); the approach has Toffoli count n(m−1).Source: §B.2 · pp. 24–25
ParallelPivoting
- ParallelPivoting divides the swaps into ⌈log2 m⌉ levels and distributes borrowed qubits across row pairs to parallelize swaps.Fig. 10 illustrates the parallelized circuit with three borrowed qubits.Source: §B.2 · pp. 25–26, Figure 10 · p. 26
Complexity
- The total Toffoli count is bounded by 2(αn′ + 1)(m′ −1), with the factor 2 arising from the borrowed-qubit parallelized controlled-swap construction.Here m′=m−j′ and n′=n−j′.Source: §B.2 · p. 26
- ParallelPivoting proceeds through ⌈log2 m′⌉ tournament levels; the depth bound includes j′+3⌈log2 m′⌉.The proof substitutes m′=m−j′ and n′=n−j′ into Proposition 5.Source: §B.2 · p. 27
B.3 RowReduction
RowReduction first scales row entries using multiplicative inverses, then eliminates entries with respect to the pivot row. Its arithmetic can be parallelized with borrowed qubits, subject to a zero-pivot convention.
RowReduction
- RowReduction has two phases: multiply each row’s entries by the inverse of its first element, then eliminate entries with respect to the pivot row.The second phase performs a straightforward arithmetic operation; the first phase is implemented using out-of-place components and working qubits.Source: In-Place Multiplication with… · pp. 27–28, §B.3 · p. 27
In-place multiplication with multiplicative inverse
- Under the assumptions that 0−1=0 and out-of-place multiplication may accumulate into a nonzero target, the first-phase operation uses two inverse operations, two multiplications, and four CNOT gates.Fig. 11 depicts the transformation and states that its ancillary registers are restored to zero.Source: In-Place Multiplication with… · p. 28, Figure 11 · p. 28
Zero pivot
- The inverse module outputs 0 on input 0, so when a pivot is zero the Fig. 11 operation preserves the input value.The circuit cannot determine beforehand which row has a zero pivot.Source: In-Place Multiplication with… · p. 28
Parallelization
- Borrowed qubits parallelize first-phase multiplications and second-phase controlled additions across rows and columns.The algorithm allocates borrowed qubits separately for the first phase, row-direction parallelization, and column-direction parallelization; Fig. 12 illustrates parallelization over GF(2).Source: In-Place Multiplication with… · pp. 28–29, Figure 12 · p. 30
Complexity
- For j=1, the second phase has (m−1)(n−1) controlled subtractions, which commute and achieve depth m−1 when m≥n.At j=1, the borrowed-qubit parallelization used in the Proposition 6 proof does not apply.Source: In-Place Multiplication with… · p. 32
C.1 Upper bounds on the Toffoli cost of multi-controlled NOT gates
The appendix summarizes a recursive decomposition for estimating Toffoli count and depth of multi-controlled NOT gates, then reports explicit upper bounds over a stated input range.
Recursive decomposition
- The decomposition method from gives recursive bounds for both Toffoli count C(m) and depth D(m) of a CmX gate.The stated base cases are C(2)=D(2)=1, C(3)=D(3)=4, and C(4)=D(4)=10.Source: §C.1 · p. 32
Explicit upper bounds
- The recursive bounds are numerically evaluated for m∈[2, 107] and compared with reference functions to obtain explicit upper bounds over that range.The reference functions are only partially legible in the supplied passage, so they are not specified here.Source: §C.1 · p. 32
- Tables 4 and 5 give non-asymptotic bounds for Algorithm 1 over GF(p^l) with p≠2 and over GF(2), respectively.The captions specify α=l⌈log2 p⌉ for the p≠2 table.Source: Table 4 · p. 33, Table 5 · p. 33
C.2 Explicit upper bounds for Algorithm 1
This appendix derives non-asymptotic circuit-cost bounds for Algorithm 1 by combining earlier appendix results and bounding the labeling costs recursively.
Explicit bounds
- Combining results from Appendices A and B yields Tables 4 and 5, the non-asymptotic counterparts of Tables 3 and 1, respectively.Source: §C.2 · p. 33
Labeling
- The appendix defines Toffoli count and depth for labeling and controlled labeling, then gives a recurrence for controlled-labeling depth.It also relates the labeling and controlled-labeling Toffoli counts through an upper-bound recurrence.Source: §C.2 · pp. 33–34
- The Toffoli-count bound for labeling is reduced recursively to smaller controlled-labeling instances plus multi-controlled-NOT costs.The derivation applies the recurrence over ⌈log2 m⌉ levels.Source: §C.2 · p. 34
D Correctness of Algorithm 1
The correctness argument compares Algorithm 1 with a classical procedure using the same pivot-selection rule and row swaps. By induction, their relevant row-echelon entries agree, while Algorithm 1 retains additional information for reversibility.
D Correctness of Algorithm 1
- The classical comparator uses the same pivot-selection rule and row-swap sequence as Algorithm 1, with row reduction performed by elementary row operations.Its pivoting tournament moves the selected row to the first row of the active submatrix; its row reduction normalizes pivot rows and eliminates entries below them.Source: D Correctness of Algorithm 1 · pp. 34–35
- For a full-column-rank input with m ≥ n, the classical procedure has a nonzero pivot at every iteration and produces a row-equivalent row-echelon form.The output has unit diagonal entries, zeros below the diagonal, and zero rows at the bottom when m > n.Source: D Correctness of Algorithm 1 · pp. 35–36
- Inductively, the quantum and classical procedures preserve matching active submatrices and produce identical pivot-row entries and trailing active submatrices at each iteration.Uncomputing pivot information does not change those parts, preserving the correspondence for the next iteration.Source: D Correctness of Algorithm 1 · p. 36
- Algorithm 1’s output P retains the information required for a pseudo row-echelon form, with remaining entries storing additional information for reversibility.Its row-echelon-relevant entries coincide with those of the classical output R.Source: D Correctness of Algorithm 1 · p. 36