Asymptotic Improvements to Quantum Circuits via Qutrits

1 INTRODUCTION

• Near-term quantum machines have severe resource constraints, making quantum-algorithm compilation and circuit optimization critical.The paper considers qutrits as an additional compilation technique for extending useful computation.Source: §1 · p. 1
• Prior qutrit work mainly achieved constant-factor improvements from the compression ratio log2(3) ≈ 1.6.Earlier approaches emphasized representing N qubits with N log2(3) qutrits.Source: §1 · p. 1
• Qutrits use a third state as temporary storage, yielding asymptotically faster runtime and improved reliability despite higher per-operation error rates.Qutrit operations are used only during an intermediate stage; inputs and outputs remain qubits.Source: §1 · p. 1
• Ancilla-free frontier circuits are constrained because every machine qubit must hold data, so qutrits can substitute for unavailable workspace.This enables efficient operation in the zone where non-data ancilla qubits are unavailable.Source: §1 · pp. 1–2
• The work contributes a qutrit circuit construction, an open-source qudit simulator with realistic noise support, and simulation evidence against qubit circuits.The construction reduces depth from 633N to 38 log2 N and gate count from 397N to 6N.Source: §1 · p. 2

2 BACKGROUND

• A qubit is a two-level quantum system that can occupy a superposition of |0⟩ and |1⟩.The squared amplitudes determine the probabilities of measuring the two basis states.Source: §2 · p. 2
• Quantum gates preserve valid probability distributions and reversibility, while measurement is the irreversible operation that produces a basis state.The X gate provides a reversible example equivalent to a classical NOT operation.Source: §2 · p. 2
• Ancilla bits make irreversible classical operations such as AND reversible by storing temporary workspace initialized to 0.A Toffoli gate preserves the inputs and writes the AND result into the ancilla.Source: §2 · p. 2, Figure 2 · p. 2
• A qutrit has three computational basis states, |0⟩, |1⟩, and |2⟩, and supports additional operations beyond qubit gates.The paper focuses on d = 3 despite the increasing number of error channels at larger d.Source: §2 · pp. 2–3
• Single-qutrit Xij gates swap two basis states while leaving the third unchanged, while X+1 and X−1 perform modular shifts.The five nontrivial permutations comprise three self-inverse swaps and two mutually inverse shifts.Source: §2 · p. 3, Figure 3 · p. 3
• Circuit width measures space cost through the number of qubits or qutrits, while depth measures time cost along the critical path.Ancilla increase width and therefore space cost.Source: §2 · p. 3

• Prior qudit work provided only a constant-factor advantage by compressing N qubits into N log2(d) qudits, while incurring higher per-qudit errors.Source: §3.1 · p. 3
• The paper introduces qutrit-based circuits that are asymptotically better than equivalent qubit-only circuits in runtime and reliability.Source: §3.1 · p. 3
• Prior qubit-only Generalized Toffoli designs trade off depth, ancilla, and gate complexity: Gidney and Barenco are ancilla-free but deep, while He has logarithmic depth but needs one ancilla per data qubit.Source: §3.2 · p. 3
• The proposed construction stores temporary results in controls’ |2⟩ states, achieving an ancilla-free design with a tree-like structure.Source: §3.2 · p. 4
• The construction is benchmarked against Gidney’s asymptotically best ancilla-free qubit circuit and an augmented single-ancilla variant.Source: §3.2 · p. 4

4.1 Key Intuition

• The circuits preserve qubit inputs and outputs while temporarily occupying the qutrit |2⟩ state, allowing insertion into qubit-only circuits.Source: §4.1 · p. 4
• The Toffoli construction elevates a control to |2⟩ exactly when both controls are |1⟩, applies X conditionally, then restores the controls.Source: §4.1 · p. 4, Figure 4 · p. 4

4.2 Generalized Toffoli Gate

• The simulated implementation decomposes each three-qutrit gate into 6 two-qutrit and 7 single-qutrit gates.Source: §4.2 · p. 4
• The Generalized Toffoli uses a binary tree whose root reaches |2⟩ only when all control leaves are |1⟩, followed by uncomputation.Source: §4.2 · pp. 4–5, Figure 5 · p. 5
• The tree reduces the number of qubits under consideration by approximately two at each level, producing logarithmic depth and linear total gate count.Source: §4.2 · p. 5
• The construction supports top-control activation on |2⟩ or |0⟩, variants required by the Incrementer circuit.Source: §4.2 · p. 5

5.1 Quantum Neuron

• The artificial quantum neuron is a promising target because its implementation is dominated by large Generalized Toffoli gates and has noise-resilient threshold behavior.Source: §5.1 · p. 5

5.2 Grover’s Algorithm

• Grover search uses a multiply-controlled gate with N = ⌈log2 M⌉ controls in post-processing after each oracle query.Source: §5.2 · p. 5
• The qutrit decomposition reduces a log M factor in Grover search time complexity to log log M without ancilla.Source: §5.2 · p. 5, Figure 6 · p. 5

5.3 Incrementer

• The Incrementer performs +1 mod 2^N and achieves O(log^2 N) depth with no ancilla, improving on prior ancilla-free constructions.Source: §5.3 · p. 5
• Its recursive carry propagation uses multiply-controlled gates whose critical path contains a chain of logarithmically many gates, yielding log2 N circuit-depth scaling.Source: §5.3 · pp. 5–6
• Although the Incrementer is useful in arithmetic circuits, making it shallower alone does not reduce the asymptotic cost of modular exponentiation or Shor’s algorithm.Source: §5.4 · p. 6

6.1 Noise Simulation

• The simulator extends Cirq from qubits to d-level qudits, includes common qutrit gates, and provides comprehensive noise simulation.Source: §6 · p. 6
• Logical correctness is checked without noise using classical non-superposition inputs, with time and space proportional to circuit width rather than exponential state-vector simulation.Source: §6 · p. 6
• Noise simulation schedules simultaneous gates into Moments, applies gate errors to acted-on qudits, and applies idle errors to every qudit.Source: §6.1 · p. 6, Figure 8 · p. 6
• Gate-error channels distinguish single- and two-qudit operations, while idle errors depend on Moment duration and whether a qutrit is excited.Source: §6.1 · pp. 6–7
• The simulator measures mean fidelity as the squared overlap between ideal and actual output states, excluding initialization and readout errors because inputs and outputs remain binary.Source: §6.1 · p. 7
• The reported noise analysis omits crosstalk errors, whose effects are device-dependent and can be mitigated through scheduling strategies.Source: §6.1 · p. 7

6.2 Simulator Efficiency

• Quantum trajectories propagate one randomly sampled state and converge to density-matrix results over repeated trials, avoiding explicit density matrices.Source: §6.2 · p. 7
• The simulator reaches circuits up to 14 qutrits wide, approximately equivalent to 22 qubits, with trials taking several minutes and running in parallel.Source: §6.2 · p. 7

Generic noise model

• The simulations use a symmetric depolarizing gate-error model, with error-channel counts scaling as d^2 for single-qudit gates and d^4 for two-qudit gates.For qubits, the model has 4 single-qubit and 16 two-qubit channels; for qutrits, 9 and 81 channels, respectively.Source: §7.1.1 · p. 8
• Idle-error modeling includes amplitude damping from higher to lower energy states, including |2⟩→|0⟩ relaxation for qutrits.The damping probabilities are λ1 for |1⟩→|0⟩ and λ2 for |2⟩→|0⟩.Source: §7.1.2 · p. 8

Superconducting QC

• Superconducting models are parameterized by gate-error probabilities and T1 relaxation, using a baseline with 10x lower gate errors and 10x longer T1 than current IBM hardware.Additional models apply another 10x improvement to T1, gate errors, or both.Source: Table 2 · p. 8, §7.2 · p. 8

Modeling scope

• The study does not vary gate speeds because the modeled errors depend on the Δt/T1 ratio, although faster gates could improve noise resilience in practice.This is a modeling choice rather than a claim that gate speed is irrelevant to physical devices.Source: §7.2 · p. 8

Trapped Ion QC

• The trapped-ion models target 171Yb+ devices, where long T1 times reduce idle errors but slow gates make photon-scattering gate errors dominant.The modeled gate durations are approximately 1 µs for single-qudit gates and 200 µs for two-qudit gates.Source: §7.3 · p. 8

Noise-model evaluation

• The trapped-ion comparison uses noise models based on experimentally derived single- and two-qutrit gate-error probabilities and gate times of approximately 1 µs and 200 µs.These models are described for three trapped-ion device variants.Source: Table 3 · p. 9

Circuit depth

• QUTRIT scales logarithmically in N, whereas both QUBIT and QUBIT+ANCILLA scale linearly in circuit depth.The comparison covers exact depths up to N = 200.Source: §8 · pp. 8–9, Figure 9 · p. 9
• A single borrowed ancilla reduces qubit circuit depth by a factor of 8, but QUTRIT still has a relatively small leading coefficient and substantially lower depth.The ancilla-assisted construction remains linear in depth.Source: §8 · pp. 8–9

Two-qudit gate counts

• All three constructions have linear two-qudit gate-count scaling, but QUTRIT’s linearity constant is 70x smaller than the ancilla-free qubit circuit’s and 8x smaller than the borrowed-ancilla circuit’s.Thus the gate-count improvement is in the linearity constant, not in asymptotic scaling.Source: §8 · p. 9, Figure 10 · p. 9

Noise-model evaluation

• The simulations evaluate 14-input Generalized Toffoli circuits, comprising 13 controls and 1 target, across three circuit benchmarks and applicable noise models.The results contain 16 bars in the reported figure and estimate mean fidelity for each circuit–noise-model pair.Source: §8 · p. 9

Simulation results

• More than 10,000x fidelity improvement separates the QUTRIT construction from the ancilla-free QUBIT benchmark.Figure 11 compares circuit constructions across noise models using 1000+ trials per bar.Source: §9 · p. 9, Figure 11 · p. 10
• 57-83% mean fidelity is achieved by qutrit constructions under three superconducting noise models, versus almost 0% for ancilla-free qubit constructions.Under the lowest-error SC+T1+GATES model, the QUBIT circuit reaches 26% while the qutrit circuit is close to 100%.Source: §9 · p. 9
• Approximately 95% fidelity is achieved by both DRESSED_QUTRIT and BARE_QUTRIT circuits, compared with 45% for the TI_QUBIT model.The dressed qutrit is more resilient to leakage errors, so its simulated advantage is described as a lower bound.Source: §9 · p. 9

Hardware implications

• Trapped-ion hardware is a particularly strong match because its all-to-all connectivity supports operations between distant qutrits.The trapped-ion models attain the highest fidelities among the discussed hardware settings.Source: §9 · p. 9
• Nearest-neighbor superconducting architectures would expand qutrit circuit depth from log N to √N because of data movement.Fully connected superconducting systems would be better matched to the construction.Source: §9 · pp. 9–10

Ancilla and parallelism

• Constant-ancilla constructions can force a choice between serializing parallel Generalized Toffoli gates to linear depth and using a linear ancilla count.This is presented as a fundamental gap between ancilla-free and constant-ancilla constructions.Source: §9 · p. 10

Scope and outlook

• The simulations cover widths up to 14 inputs, while the authors expect larger advantages from asymptotically lower depth and reduced idle errors.The paper also expects benefits for Section 5 circuits using Generalized Toffoli, though those circuits were not explicitly simulated.Source: §9 · p. 10
• The authors argue that qutrit circuits improve near-term quantum computing through asymptotically faster ancilla-free circuits, better linearity constants, and higher reliability.They identify arithmetic circuits as a future application area for redesign using qutrits.Source: §9 · p. 10

Noise-model methodology

• The noise-modeling methodology begins with a generic parametrized model intended to apply across quantum systems.The paper then instantiates this model for near-term superconducting quantum computers and 171Yb+ trapped ions.Source: A DETAILED NOISE MODEL · p. 11

Generic noise model

• The Kraus operator formalism specifies quantum noise through matrices {K_i}, each representing an error channel.For an initial state σ = |Ψ⟩⟨Ψ|, the formalism expresses the noisy evolution as E(σ).Source: §A.1 · p. 11
• The dagger symbol denotes the matrix conjugate-transpose in the noise-model equation.This defines the matrix operation used in the formalism.Source: §A.1 · p. 11
• A single qubit has four modeled error channels: no-error, bit flip, phase flip, and phase+bit flip.These channels are expressed using products of Pauli matrices.Source: §A.1.1 · p. 11

Qubit gate errors

• The single-qubit gate model uses a symmetric depolarizing channel in which all non-identity error terms have equal probability p1.The model is presented as a standard Pauli-channel assumption for noise simulators.Source: §A.1.1 · p. 11
• Two-qubit errors use Cartesian products of single-qubit Kraus operators, with K_jklm = X^jZ^k ⊗ X^lZ^m and error-term probability p2.The resulting channel includes the no-error identity operation and combined bit- and phase-flip errors.Source: §A.1.1 · p. 11

Qutrit gate errors

• Qutrit gate errors use generalized Pauli matrices, whose Cartesian products form a basis for all 3×3 matrices and the corresponding Kraus operators.This construction accounts for the larger set of possible qutrit error channels.Source: §A.1.1 · p. 11
• The two-operand qutrit no-error probability is 1−80p2, compared with 1−15p2 for the corresponding qubit model.The paper identifies this reduction as the dominant effect of using qutrits instead of qubits in this noise model.Source: §A.1.1 · p. 11

Amplitude damping

• Amplitude damping is modeled for both qutrits and qubits, while incoherent channel probabilities depend on the current state through ||K_i|ψ⟩||2.The qutrit amplitude-damping Kraus operators are specified separately from the generic gate-error model.Source: §A.1.2 · p. 11

Device noise models

• The superconducting-device noise models are parameterized by p1, p2, λ1, and λ2, with λ_m = 1−e^(−mΔt/T1).Here Δt is the idle duration and T1 is the associated qubit lifetime.Source: §A.2 · p. 11
• The selected models are TI_QUBIT, BARE_QUTRIT, and DRESSED_QUTRIT, differing mainly in clock-state use, idle-error magnitude, and experimental preparation resources.TI_QUBIT and DRESSED_QUTRIT have very small idle errors, whereas BARE_QUTRIT requires fewer preparation resources but suffers more idle error.Source: §A.3 · p. 12