PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic Improvements to Quantum Circuits via Qutrits

Pranav Gokhale, Jonathan M. Baker, Casey Duckering, Natalie C. Brown, Kenneth R. Brown, Frederic T. Chong

arXiv:1905.10481v1quant-phcs.ET

TL;DR

The paper addresses the limited resource efficiency of qubit-only circuits, especially when ancilla are unavailable. It uses qutrits as temporary intermediate storage, develops simulation tools and noise models, and reports faster, lower-cost, more reliable constructions. The results support qutrits as a path toward scaling near-term quantum computation, while connectivity and eventual ancilla trade-offs remain boundaries.

  • Problem

    Severe quantum-resource constraints and the limited prior work on qutrits motivate seeking improvements beyond the constant-factor gain from log2(3) compression.

  • Method

    The paper uses the third qutrit state as temporary storage in ancilla-free circuits, while retaining qubit inputs and outputs, and evaluates them with an open-source simulator and realistic noise models.

  • Results

    The qutrit construction achieves more than 10,000x higher fidelity than the ancilla-free qubit benchmark in Figure 11, with 57-83% mean fidelity across several superconducting models and approximately 95% for trapped-ion qutrit models.

  • Takeaways & Limitations

    The results support qutrits as a near-term path for extending the frontier of computable quantum circuits and scaling quantum computation.

  • Takeaways & Limitations

    On nearest-neighbor 2D superconducting architectures, accounting for data movement would increase the qutrit circuit depth from log N to √N.

Abstract

from arXiv · show

Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu$trits$. Past work with qutrits has demonstrated only constant factor improvements, owing to the $\log_2(3)$ binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla--a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation.

1 INTRODUCTION

The paper addresses resource constraints in near-term quantum computing by using qutrits to replace ancilla workspace. Its construction achieves asymptotically faster, lower-cost circuits and improved reliability while retaining qubit inputs and outputs.

  • 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.
  • 1 INTRODUCTION: 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.

2 BACKGROUND

The background defines qubits, reversible quantum operations, circuit costs, and qutrits as three-level systems with additional gate operations. It motivates qutrits for reducing resource costs in reversible circuits such as Generalized Toffoli constructions.

  • 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.
  • 2 BACKGROUND: 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.
  • 2 BACKGROUND: 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.
  • 2 BACKGROUND: 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.
  • 2 BACKGROUND: 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.
  • 2 BACKGROUND: 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.

3 PRIOR WORK

Prior qudit work primarily offered constant-factor compression benefits, while this paper introduces qutrit circuits that improve both asymptotic runtime and reliability without ancilla.

  • Prior qudit work provided only a constant-factor advantage by compressing N qubits into N log2(d) qudits, while incurring higher per-qudit errors.
  • The paper introduces qutrit-based circuits that are asymptotically better than equivalent qubit-only circuits in runtime and reliability.
  • 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.
  • The proposed construction stores temporary results in controls’ |2⟩ states, achieving an ancilla-free design with a tree-like structure.
  • The construction is benchmarked against Gidney’s asymptotically best ancilla-free qubit circuit and an augmented single-ancilla variant.

4 CIRCUIT CONSTRUCTION

The circuit construction uses temporary qutrit states to implement multiply-controlled operations while preserving qubit inputs and outputs. A tree of intermediate |2⟩ states yields logarithmic depth and linear gate count without ancilla.

  • 4.1 Key Intuition: The circuits preserve qubit inputs and outputs while temporarily occupying the qutrit |2⟩ state, allowing insertion into qubit-only circuits.
  • 4.1 Key Intuition: The Toffoli construction elevates a control to |2⟩ exactly when both controls are |1⟩, applies X conditionally, then restores the controls.
  • 4.2 Generalized Toffoli Gate: The simulated implementation decomposes each three-qutrit gate into 6 two-qutrit and 7 single-qutrit gates.
  • 4.2 Generalized Toffoli Gate: The Generalized Toffoli uses a binary tree whose root reaches |2⟩ only when all control leaves are |1⟩, followed by uncomputation.
  • 4.2 Generalized Toffoli Gate: The tree reduces the number of qubits under consideration by approximately two at each level, producing logarithmic depth and linear total gate count.
  • 4.2 Generalized Toffoli Gate: The construction supports top-control activation on |2⟩ or |0⟩, variants required by the Incrementer circuit.

5 APPLICATION TO ALGORITHMS

The qutrit multiply-controlled-gate primitive targets quantum neurons, Grover search, and incrementers. It reduces Grover’s relevant factor from log M to log log M and gives ancilla-free logarithmic-depth incrementers.

  • 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.
  • 5.2 Grover’s Algorithm: Grover search uses a multiply-controlled gate with N = ⌈log2 M⌉ controls in post-processing after each oracle query.
  • 5.2 Grover’s Algorithm: The qutrit decomposition reduces a log M factor in Grover search time complexity to log log M without ancilla.
  • 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.
  • 5.3 Incrementer: Its recursive carry propagation uses multiply-controlled gates whose critical path contains a chain of logarithmically many gates, yielding log2 N circuit-depth scaling.
  • 5.3 Incrementer: 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.

6 SIMULATOR

The authors extend Cirq into an open-source qutrit simulator with gate, idle, and trajectory-based noise modeling. The simulator evaluates fidelity while accounting for gate duration, state-dependent idle errors, and circuit depth.

  • 6.1 Noise Simulation: The simulator extends Cirq from qubits to d-level qudits, includes common qutrit gates, and provides comprehensive noise simulation.
  • 6.1 Noise Simulation: 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.
  • 6.1 Noise Simulation: Noise simulation schedules simultaneous gates into Moments, applies gate errors to acted-on qudits, and applies idle errors to every qudit.
  • 6.1 Noise Simulation: Gate-error channels distinguish single- and two-qudit operations, while idle errors depend on Moment duration and whether a qutrit is excited.
  • 6.1 Noise Simulation: 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.
  • 6.1 Noise Simulation: The reported noise analysis omits crosstalk errors, whose effects are device-dependent and can be mitigated through scheduling strategies.
  • 6.2 Simulator Efficiency: Quantum trajectories propagate one randomly sampled state and converge to density-matrix results over repeated trials, avoiding explicit density matrices.
  • 6.2 Simulator Efficiency: The simulator reaches circuits up to 14 qutrits wide, approximately equivalent to 22 qubits, with trials taking several minutes and running in parallel.

7 NOISE MODELS

The paper models realistic near-term superconducting and trapped-ion devices, incorporating gate errors, relaxation, and device-specific operating conditions. These models account for the higher error opportunities of qutrit operations and motivate projected hardware improvements.

  • 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.
  • Generic noise model: 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⟩.
  • 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.
  • 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.
  • 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.

8 RESULTS

The qutrit construction outperforms both qubit benchmarks in circuit depth and two-qudit gate-count constants. Simulations evaluate all three constructions on a 14-input Generalized Toffoli across the applicable noise models.

  • 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.
  • 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.
  • Circuit depth: 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.
  • 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.
  • 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.

9 DISCUSSION

The QUTRIT construction achieves substantially higher simulated fidelity than qubit baselines while avoiding ancilla, but hardware connectivity can affect its depth advantage. The authors position qutrits as a near-term route to more reliable, scalable quantum computation.

  • 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.
  • Simulation results: 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%.
  • Simulation results: 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.
  • 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.
  • Hardware implications: 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.
  • 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.
  • 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.
  • Scope and outlook: 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.

A DETAILED NOISE MODEL

The paper models realistic near-term quantum hardware by combining a generic parametrized noise model with device-specific superconducting and trapped-ion parameters.

  • 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.

A.1 Generic Noise Model

The generic quantum noise model represents system evolution through error-channel matrices in the Kraus operator formalism, with qubit channels including standard Pauli errors.

  • 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(σ).
  • Generic noise model: The dagger symbol denotes the matrix conjugate-transpose in the noise-model equation.This defines the matrix operation used in the formalism.
  • Generic noise model: 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.

A.1.1 Gate Errors.

The paper models gate errors for qubits and qutrits with Kraus-operator noise channels, including depolarizing and amplitude-damping effects. Because qutrits have more possible error channels, their two-operand no-error probability decreases from 1−15p2 to 1−80p2.

  • 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.
  • Qubit gate errors: 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.
  • 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.
  • Qutrit gate errors: 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.
  • 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.
  • 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.
  • Device noise models: 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.
Loading 1905.10481v1…