Source-linked AI summary
Qudits and high-dimensional quantum computing
Yuchen Wang, Zixuan Hu, Barry C. Sanders, Sabre Kais
TL;DR
Qudit quantum computing addresses the limited two-level structure of qubits by using multi-level computational units. This review surveys qudit gates, algorithms, models, and physical implementations, reporting reduced qudit and gate requirements in several constructions. It also notes that qudit research remains less developed and that practical advantages vary across physical apparatuses.
Problem
Qudits receive less theoretical and experimental attention than qubits despite their larger state spaces and potential computational advantages.
Method
The review synthesizes qudit circuit construction, gate universality, algorithms, alternative computational models, and physical implementations.
Results
Qudit constructions reduce resource requirements, including a (log_2 d)^2 scaling advantage and Toffoli decompositions using 2n−1 or 2n−3 gates instead of 12n−11.
Takeaways & Limitations
Qudit systems can exploit extra physical levels and multi-level control operations across photonic, superconducting, trapped-ion, magnetic, and molecular platforms.
Takeaways & Limitations
Qudit advantages vary with the particular physical apparatus, while the field still has comparatively limited theoretical and experimental attention.
Abstract
from arXiv · showhide
Qudit is a multi-level computational unit alternative to the conventional 2-level qubit. Compared to qubit, qudit provides a larger state space to store and process information, and thus can provide reduction of the circuit complexity, simplification of the experimental setup and enhancement of the algorithm efficiency. This review provides an overview of qudit-based quantum computing covering a variety of topics ranging from circuit building, algorithm design, to experimental methods. We first discuss the qudit gate universality and a variety of qudit gates including the pi/8 gate, the SWAP gate, and the multi-level-controlled gate. We then present the qudit version of several representative quantum algorithms including the Deutsch-Jozsa algorithm, the quantum Fourier transform, and the phase estimation algorithm. Finally we discuss various physical realizations for qudit computation such as the photonic platform, iron trap, and nuclear magnetic resonance.
1 Introduction to qudits
Qudits extend qubits with multiple levels, enlarging the computational state space and enabling simultaneous control operations. The review surveys qudit circuits, algorithms, and physical implementations.
- Motivation: Qudits are multi-level quantum units that provide a larger state space and can perform multiple control operations simultaneously.These properties are associated with reduced circuit complexity, simpler experimental setups, and improved algorithm efficiency.
- Scope: Qudit-based systems apply beyond circuit-model computers, including adiabatic and topological quantum computing devices.
- Scope: Qudit computation can be implemented on photonic, continuous-spin, ion-trap, nuclear-magnetic-resonance, and molecular-magnet platforms.
- Review coverage: The review addresses qudit circuit building, algorithm design, and experimental methods.
- Review coverage: It presents high-dimensional generalizations of widely used quantum gates and discusses the universality of qudit gates.
- Review coverage: The article covers qudit versions of major quantum algorithms and reviews models beyond circuits alongside physical realizations.Its organization includes algorithms, measurement-based, adiabatic, and topological models, and physical-platform implementations.
2 Quantum gates for qudits
A qudit is a d-level quantum computational element represented in a d-dimensional Hilbert space. Qudit gates transform these states, and the section reviews their properties, universality, examples, and efficiency.
- Qudit states: A qudit is a quantum version of a d-ary digit whose state lies in the d-dimensional Hilbert space H_d.Its computational basis contains |0⟩ through |d −1⟩.
- Qudit states: A general qudit state is a superposition of the d computational basis states with complex amplitudes α_0 through α_d−1.
- Qudit states: The amplitudes satisfy the normalization condition |α_0|^2 + |α_1|^2 + · · · + |α_d−1|^2 = 1.
- Qudit gates: Qudits can replace qubits as basic computational elements, with their states transformed by qudit gates.
- Section scope: The section reviews universal gate criteria, fundamental gate sets, gate examples, qubit comparisons, and geometric efficiency bounds.
2.1 Criteria for universal qudit gates
The review describes universal qudit gate sets, their decomposition of arbitrary unitaries, and examples generalizing familiar qubit gates. These constructions can reduce representation and gate requirements relative to qubits.
- Universality criteria: A universal qudit gate set can approximate any arbitrary unitary transformation on the relevant Hilbert space with acceptable error.
- Universal sets: Two noncommuting single-qudit gates together with a two-qudit gate are sufficient to simulate arbitrary U ∈ U(d^n) with arbitrary precision.
- Universal sets: The reviewed construction uses single- and two-qudit gates, spectral or eigen-decomposition, controlled operations, and two-qudit decompositions to synthesize arbitrary unitaries.The procedure decomposes multi-qudit-controlled gates into combinations of two-qudit controlled rotations and permutations.
- Universal sets: The gate set consisting of X(l)_d, Z_d, and C_2[R_d] is proved universal for qudit quantum computation.The proof proceeds through eigen-decomposition, controlled-gate decomposition, and reduction to two-qudit gates.
- Efficiency advantages: Qudits require n_2 = log_d N qudits for an N-dimensional system versus n_1 = log_2 N qubits, giving reduction factor k = log_2 d.
- Efficiency advantages: The Muthukrishnan-Stroud construction has a (log_2 d)^2 scaling advantage over the qubit case and an extra factor of n reduction in gate requirements.The reviewed decomposition gives L ⩽ 6nd^(2n) + nd^n and uses fewer free parameters for primitive gates.
2.2 Examples of qudit gates
The review presents qudit versions of key gates, emphasizing their roles in universality, circuit construction, and resource reduction. Examples include generalized π/8, SWAP, Toffoli, and multi-level-controlled gates.
- 2.2.1 Qudit versions π/8 gate: The qudit π/8 gate generalizes the non-Clifford qubit gate to prime dimensions d > 2 and supports universal quantum computation.Its generalized form is also identified with maximally robust qudit gates for fault-tolerant computation.
- 2.2.1 Qudit versions π/8 gate: The generalized qudit π/8 gate has applications in teleportation, transversal implementation, unknown-gate learning, assisted quantum computation, and magic-state distillation.Magic-state distillation protocols were established first for qutrits and later extended to all prime-dimensional qudits.
- 2.2.2 Qudit SWAP gate: A Hermitian controlled gate C̃X enables a qudit SWAP circuit using one gate type, with C̃X decomposed from QFT and selective phase-shift operations.The resulting SWAP gate can be implemented on multilevel systems and connects systems restricted to nearest-neighbour interactions.
- 2.2.3 Simplified qubit Toffoli gate with a qudit: For n-qubit-controlled Toffoli gates, a single (n+1)-level target carrier uses 2n−1 two-qubit gates instead of 12n−11 in the best previously known realization.The target carrier requires one extra level for each additional control qubit, and the construction extends to multi-qudit-controlled gates.
- 2.2.4 Qudit multi-level controlled gate: A qudit multiplexer applies a distinct target operation for each control-qudit state, using controlled operations and shifting gates to exploit all d control levels.This multi-value-controlled gate applies a unique operation to the target for every unique control state.
2.3 Geometrically quantifying qudit-gate efficiency
The review quantifies qudit-gate efficiency by replacing gate-count lower bounds with shortest-geodesic distances on SU(d^n), using generalized Gell-Mann matrices and penalties for many-body interactions. The resulting theorems bound approximate synthesis with one- and two-qudit gates.
- Geometric formulation: Circuit complexity is modeled as a Riemannian-geometry problem, where synthesizing U corresponds to finding the minimal geodesic from I to U.The unitary evolution is generated by a time-dependent Hamiltonian and evaluated through a cost function on Hamiltonian controls.
- Geometric formulation: Generalized Gell-Mann matrices provide the d-dimensional Hamiltonian basis used to represent qutrit and broader qudit operations.The basis construction extends from SU(d) to SU(d^n) by tensor-like operators acting on selected qudits.
- Cost function: One- and two-body interactions generate all higher-body interactions, while the metric assigns a penalty to three- and more-body terms.The penalty enters the cost function used to define distances in SU(3^n).
- Synthesis bounds: For qutrits, O(n^k d(I,U)^3) one- and two-qutrit gates lower-bound synthesis of an approximation U_A satisfying ∥U−U_A∥≤c.The bound applies for U in SU(3^n) and constant c.
- Synthesis bounds: For any small constant ε, each U_A∈SU(d^n) can be synthesized with O(ε^-2) one- and two-qudit gates while maintaining ∥U−U_A∥≤ε.The approximation relation δ=d(I,U)/N≤ε links nonlocal gate cost to synthesis error.
3 Quantum algorithms using qudits
Qudit algorithms exploit the larger information capacity of multi-dimensional states, either by directly generalizing qubit algorithms or by using qudit dimensionality in key subroutines.
- Overview: A qudit can store and process more information than a qubit because its state space is multidimensional.The reviewed algorithms include both direct qubit generalizations and procedures that use multidimensional states centrally.
3.1 Qudit oracle-decision algorithm
Qudit oracle-decision algorithms extend parity, Deutsch-Jozsa, and related procedures to multi-valued functions, often using a single query or single qudit. These examples demonstrate algorithmic behavior enabled by qudit state spaces and, in one case, contextuality without entanglement.
- Parity determining algorithm: The parity algorithm generalizes to arbitrary d-dimensional qudits, although its higher-dimensional speedup is not exponential.The model problem itself has no significant applications according to the review.
- Contextuality and related algorithms: The reviewed qudit contextual algorithm uses a single qudit without quantum or classical correlations to study quantum speedup beyond entanglement.The paper frames it as a faster-than-classical example based on contextuality.
- Parity determining algorithm: A single-qutrit parity algorithm applies one permutation oracle and distinguishes even from odd permutations after an inverse Fourier transform.The algorithm determines the parity with one application of the permutation on one qutrit and has been implemented in NMR and optical systems.
- Deutsch-Jozsa algorithm: The qudit Deutsch-Jozsa algorithm distinguishes constant from balanced multi-valued functions and can recover affine-function coefficients except for the constant term.The coefficients A_1,...,A_r are obtained by measuring the x-register output |A_1,...,A_r⟩.
- Deutsch-Jozsa algorithm: For the qudit Deutsch-Jozsa procedure, all-zero x-register measurement identifies a constant function; any other outcome identifies a balanced function.The review presents this as an analogy to the qubit algorithm's reasoning.
- Deutsch-Jozsa algorithm: The qudit Deutsch-Jozsa generalization also supports applications such as affine-map analysis, image-processing texture distinctions, and secure quantum-key protocols.These applications are described as potential or possible uses, while the algorithm is mainly of theoretical interest.
- Bernstein-Vazirani algorithm: The Bernstein-Vazirani generalization determines an unknown string from a function encoding a bit-wise inner product, extending the Deutsch-Jozsa framework.The review states that the conventional algorithm outperforms the best classical algorithm by a factor of N.
3.2 Qudit algorithms for the hidden Abelian subgroup problems.
Qudit versions of hidden-subgroup algorithms include the quantum Fourier transform and phase estimation, implemented with generalized Hadamard, phase, controlled, and SWAP gates. The review reports improved approximation behavior and reduced resource requirements as qudit dimension increases.
- Quantum Fourier transform: The qudit quantum Fourier transform acts in an N-dimensional system encoded by n d-dimensional qudits, with N=d^n.It transforms the computational basis into a new basis and can be implemented using generalized Hadamard and phase gates.
- Quantum Fourier transform: Controlled phase gates apply R_d^k to a target qudit according to the control state, and final SWAP gates restore the required output order.The SWAP gates are applied at the end but are not explicitly drawn in Figure 10.
- Quantum Fourier transform: Qudit QFT approximation error decreases exponentially with d, and the review reports smaller error bounds than in the binary case.The QFT is presented as a crucial subroutine for many qudit algorithms.
- Phase-estimation algorithm: Qudit phase estimation uses a t-qudit first register and a second register storing an eigenvector |u⟩, with controlled U operations producing phase kick-back.Applying the inverse QFT to the first register yields the eigenvalue representation for measurement.
- Phase-estimation algorithm: The phase-estimation circuit obtains the phase by inverse Fourier transforming and measuring the first-register qudits.The first register's size depends on the desired estimation accuracy.
- Phase-estimation algorithm: Qudit phase estimation significantly reduces the required number of qudits, while its error rate decreases exponentially as qudit dimension increases.The review connects these properties to applications including factoring, quantum simulation, linear equations, and quantum counting.
- Applications: Because Shor's order-finding procedure is a direct application of phase estimation, qudit QFT and PEA provide the basis for higher-dimensional factoring algorithms.The review also discusses resource analyses for generic ternary and metaplectic topological platforms.
3.3 Quantum search algorithm with qudits
Qudit Grover search expands the working space while simplifying the iteration operator. Replacing the generalized Hadamard with the F gate enables an equal-weight superposition through a single physical multipod interaction.
- Algorithmic motivation: Qudit Grover search expands the computational space by increasing each information carrier’s dimension.This addresses practical limits on the number of working qubits.
- Algorithmic structure: Grover iteration repeatedly applies an oracle that phase-shifts the marked state and a reflection about the average.The combined operations form Grover’s operator G, amplifying the marked state in O(√N) steps for an N-dimensional search space.
- Qudit Grover operator: The qudit F gate replaces the Hadamard gate by driving |0k⟩ into an equal-weight superposition.The circuit illustration identifies F as the proposed single-qudit gate used in the qudit Grover iteration.
- Physical realization: A multipod system realizes F through one physical interaction among d degenerate qudit states coupled to a common ancilla state.The coupling uses two-photon Raman processes, with the multipod dynamics reducible to a two-state solution.
- Physical realization: The proposed F-gate construction minimizes algorithmic steps and their duration, while improving protection against decoherence or imperfections.The review describes this as a simple and natural realization of Grover’s algorithm in qudits.
4 Alternative models of quantum computing with qudits
Alternative qudit computation models extend beyond gate-based circuits, but several remain sparsely explored. Existing work covers graph-state preparation, adiabatic factorization proposals, and topological schemes using parafermions.
- Overview: Qudit versions of measurement-based, adiabatic, and topological quantum computing remain barely explored compared with gate-based models.The review summarizes the current status of these alternative approaches.
- Measurement-based quantum computing: Measurement-based qudit quantum computing is unexplored to date, with preparatory work on qudit graph states and qudit-based error correction reported.The reported error-correction approach envisions cluster states comprising qudits.
- Adiabatic quantum computing: Adiabatic quantum computing encodes a problem solution in a Hamiltonian ground state and reaches it by slow evolution under the adiabatic condition.Its natural correspondence to satisfiability problems is identified as an advantage.
- Adiabatic quantum computing: Only one qudit adiabatic proposal is identified: factorization on two possibly different-dimensional qudits using a hybrid two-qudit gate.The proposal uses a time-dependent effective Hamiltonian and radio-frequency magnetic-field pulses.
- Topological quantum computing: For topological qudit computing, Zd parafermion braiding provides entangling operations and generates all single-qudit Clifford gates modulo phase terms.A non-Clifford gate from the Aharonov–Casher effect combined with braiding yields a universal gate set.
5 Implementations of qudits and algorithms
Qudit computation has been implemented or proposed across photonic, ion-trap, NMR, and molecular-magnet platforms. These studies demonstrate high-dimensional gates, algorithms, measurements, and phase estimation, with reported experimental fidelities and coherence times.
- Platform overview: Many physical systems provide more than two available states, and qudit implementations can extend these systems to higher levels and multi-qudit interactions.The review identifies photons, superconducting systems, trapped ions, and magnetic and non-magnetic molecules as examples.
- Photonic systems: Photonic platforms support high-dimensional transformations and entanglement using frequency modes, while a single photon can encode two qutrits in time-bin and frequency-bin degrees of freedom.This encoding bypasses the difficulty of deterministic two-photon interactions for a proof-of-principle qutrit phase estimation experiment.
- Photonic systems: Photonic phase estimation measures control-register qutrit counts to obtain phase information from the target register.The experiment sends photonic qutrits through control and target registers before measuring the control state.
- Photonic systems: The estimated phase is selected by minimizing the mean-square error between measured and theoretical photon-count results.Counts E0, E1, and E2 correspond to photons detected in the three frequency-bin qutrit states.
- Photonic systems: The photonic experiments estimate an eigenvector phase and an arbitrary phase, with repeated trials enabling eigenvalue estimation from the resulting statistical distribution.The estimated phases for U1 and U2 are reported in Table 1.
- Ion-trap systems: Ion-trap systems can perform arbitrary single-qutrit gates and a control-not gate, which together form a universal set.The logical qutrit uses three electronic levels, with transitions driven by classical fields and interactions mediated through shared phonon states.
- Ion-trap systems: An ion-trap evolution operator enables coherent operations on any two logical states, allowing arbitrary one-qutrit gates through manipulation of coupling parameters.The operator functions as a single-qutrit gate within the restricted three-dimensional space.
- Ion-trap systems: Ion-trap qutrit designs support measurements distinguishing |0⟩, |1⟩, and |2⟩, and combine single- and two-qutrit controlled gates for algorithms such as the quantum Fourier transform.A conditional two-qutrit gate is achieved through the ions’ center-of-mass motion.
6 Summary and future outlook of qudit system
The review presents qudits as offering larger computational spaces and potential benefits in circuit design, physical implementation, and applications. It also identifies substantial open challenges in benchmarking, gate characterization, error correction, and broader theoretical and experimental development.
- Future outlook: The review covers qudit gates, algorithms, alternative computation models, and implementations as a summary of recent developments and an introduction for newcomers.It identifies harder-to-implement universal gates, benchmarking, gate characterization, and error correction as challenges.
- Summary of advantages: Qudit systems provide more degrees of freedom and larger computational spaces, with reported advantages including shorter computation time and lower resource requirements.The review frames these benefits as advantages over qubit systems.
- Summary of advantages: Qudit gate decompositions can reduce the number of carriers and elementary gates needed to represent or synthesize arbitrary unitaries.The Muthukrishnan–Stroud method has a (log2 d)^2 scaling advantage, while another scheme adds a factor of n reduction in gate requirement.
- Summary of advantages: Physical platforms can use extra available states more efficiently, and photonic qudits can support multi-level controlled operations.The review lists photons, superconducting systems, trapped ions, and molecular systems among relevant platforms.
- Summary of advantages: Qudits offer higher noise resilience than qubits in quantum communication, with increasing noise-level tolerance as dimension increases in a photonic OAM example.The review relates this comparison to quantum bit error rate.
- Summary of advantages: The review concludes that qudits have advantages in circuit design and physical implementation and may outperform qubits in various applications.It presents this as a potential rather than a universal demonstrated outcome.
- Future outlook: Qudit research has received less theoretical and experimental attention than qubit research, leaving directions involving scaling, benchmarking, error correction, and connections to continuous-variable computing.The review describes these topics as ripe for exploration.
Funding
The authors acknowledge financial support from the National Science Foundation, NSERC, and the Alberta Government.
- The National Science Foundation provided financial support under award number 1839191-ECCS.
- BCS acknowledges financial support from NSERC.
- BCS acknowledges financial support from the Alberta Government.