Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures

Abstract

We determine the cost of performing Shor's algorithm for integer factorization on a ternary quantum computer, using two natural models of universal fault-tolerant computing: (i) a model based on magic state distillation that assumes the availability of the ternary Clifford gates, projective measurements, classical control as its natural instrumentation set; (ii) a model based on a metaplectic topological quantum computer (MTQC). A natural choice to implement Shor's algorithm on a ternary quantum computer is to translate the entire arithmetic into a ternary form. However, it is also possible to emulate the standard binary version of the algorithm by encoding each qubit in a three-level system. We compare the two approaches and analyze the complexity of implementing Shor's period finding function in the two models. We also highlight the fact that the cost of achieving universality through magic states in MTQC architecture is asymptotically lower than in generic ternary case.

22 pages, 7 figures; v3: significant overhaul; this version focuses on the use of true ternary vs. emulated binary encoding

References in corpus (13)

• Non-Abelian Anyons and Topological Quantum Computation
• Multi-photon entanglement in high dimensions
• Magic state distillation with low overhead
• A new quantum ripple-carry addition circuit
• Novel constructions for the fault-tolerant Toffoli gate
• Fast Quantum Modular Exponentiation
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Multilevel distillation of magic states for quantum computing
• Qudit versions of the qubit "pi-over-eight" gate
• Shor's algorithm on a nearest-neighbor machine
• Faster Quantum Number Factoring via Circuit Synthesis
• Factoring using 2n+2 qubits with Toffoli based modular multiplication
• Improved Quantum Ternary Arithmetics

Cited by in corpus (68)

• Multidimensional quantum entanglement with large-scale integrated optics
• Twisted Photons: New Quantum Perspectives in High Dimensions
• Qudits and high-dimensional quantum computing
• High-dimensional quantum communication: benefits, progress, and future challenges
• High-Dimensional Single-Photon Quantum Gates: Concepts and Experiments
• Experimental GHZ Entanglement beyond Qubits
• Orbital angular momentum of photons and the entanglement of Laguerre-Gaussian modes
• High-Fidelity Qutrit Entangling Gates for Superconducting Circuits
• Asymptotic Improvements to Quantum Circuits via Qutrits
• Quantum Indistinguishability by Path Identity: The awakening of a sleeping beauty
• Computer-inspired concept for high-dimensional multipartite quantum gates
• Scalable quantum computing with qudits on a graph
• Time-Sliced Quantum Circuit Partitioning for Modular Architectures
• Programmable Heisenberg interactions between Floquet qubits
• Quantum Error Correction of Qudits Beyond Break-even
• Conceptual understanding through efficient inverse-design of quantum optical experiments
• Decomposing the generalized Toffoli gate with qutrits
• Realizing quantum gates with optically-addressable ${}^{171}$Yb${}^{+}$ ion qudits
• Resource-Efficient Quantum Computing by Breaking Abstractions
• Efficient realization of quantum algorithms with qudits
• Quantum capacity analysis of multi-level amplitude damping channels
• Complete unitary qutrit control in ultracold atoms
• Qudits for decomposing multiqubit gates and realizing quantum algorithms
• Canonical forms for single-qutrit Clifford+T operators
• Demonstration of a parity-time symmetry breaking phase transition using superconducting and trapped-ion qutrits
• Emulating two qubits with a four-level transmon qudit for variational quantum algorithms
• Continuous dynamical decoupling of optical ${}^{171}$Yb${}^{+}$ qudits with radiofrequency fields
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Exploring Ququart Computation on a Transmon using Optimal Control
• Randomized benchmarking for qudit Clifford gates
• Dissipative stabilization of high-dimensional GHZ states for neutral atoms
• Universal quantum computing with qubits embedded in trapped-ion qudits
• Towards multiqudit quantum processor based on a ${}^{171}$Yb${}^{+}$ ion string: Realizing basic quantum algorithms
• Generalized Toffoli gate decomposition using ququints: Towards realizing Grover's algorithm with qudits
• One-Dimensional Lazy Quantum walk in Ternary System
• Qutrit Circuits and Algebraic Relations: A Pathway to Efficient Spin-1 Hamiltonian Simulation
• Qutrit ZX-calculus is Complete for Stabilizer Quantum Mechanics
• QuDiet: A Classical Simulation Platform for Qubit-Qudit Hybrid Quantum Systems
• Time-Efficient Qudit Gates through Incremental Pulse Re-seeding
• Certifying dimension of quantum systems by sequential projective measurements
• Circuit Design for $k$-coloring Problem and Its Implementation in Any Dimensional Quantum System
• Non-Pauli errors can be efficiently sampled in qudit surface codes
• Broadcasting of quantum correlations in qubit-qudit systems
• The Qupit Stabiliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification
• Efficient characterization of qudit logical gates with gate set tomography using an error-free Virtual-Z-gate model
• The qudit Pauli group: non-commuting pairs, non-commuting sets, and structure theorems
• Building Qutrit Diagonal Gates from Phase Gadgets
• Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits
• Qompress: Efficient Compilation for Ququarts Exploiting Partial and Mixed Radix Operations for Communication Reduction
• Scaling W state circuits in the qudit Clifford hierarchy
• Ternary Logic Design in Topological Quantum Computing
• Improved Quantum Ternary Arithmetics
• Dissipative phase transition: from qubits to qudits
• Demonstration of Discrete-Time Quantum Walks and Observation of Topological Edge States in a Superconducting Qutrit Chain
• Efficient Experimental Qudit State Estimation via Point Tomography
• High robustness quantum walk search algorithm with qudit Householder traversing coin, machine learning study
• A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits
• Transpiling quantum assembly language circuits to a qudit form
• Experimental Approach to Demonstrating Contextuality for Qudits
• Heralded High-Dimensional Photon-Photon Quantum Gate
• Efficient quantum state tomography with auxiliary Hilbert space
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Transversal AND in Quantum Codes
• Constructing all qutrit controlled Clifford+T gates in Clifford+T
• Reliable computation by large-alphabet formulas in the presence of noise
• Quantum Algorithms in Cybernetics
• Sequences of selective rotation operators to engineer interactions for quantum annealing on three qutrits
• Experimental Demonstration of Efficient High-dimensional Quantum Gates with Orbital Angular Momentum