Approximate stabilizer rank and improved weak simulation of Clifford-dominated circuits for qudits

Abstract

Bravyi and Gosset recently gave classical simulation algorithms for quantum circuits dominated by Clifford operations. These algorithms scale exponentially with the number of T-gate in the circuit, but polynomially in the number of qubits and Clifford operations. Here we extend their algorithm to qudits of odd prime dimensions. We generalize their approximate stabilizer rank method for weak simulation to qudits and obtain the scaling of the approximate stabilizer rank with the number of single-qudit magic states. We also relate the canonical form of qudit stabilizer states to Gauss sum evaluations. We give an O(n^3) algorithm to calculating the inner product of two n-qudit stabilizer states.

arXiv comment14 pages, 2 figures

References in corpus (36)

• Quantum Teleportation is a Universal Computational Primitive
• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Characterizing Quantum Supremacy in Near-Term Devices
• Contextuality supplies the magic for quantum computation
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Positive Wigner functions render classical simulation of quantum computation efficient
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Methodology for quantum logic gate constructions
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Negativity and contextuality are equivalent notions of nonclassicality
• Trading classical and quantum computational resources
• The SIC Question: History and State of Play
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• 0.5 Petabyte Simulation of a 45-Qubit Quantum Circuit
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• The completeness of quantum theory for predicting measurement outcomes
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Quasi-quantization: classical statistical theories with an epistemic restriction
• Quantum from principles
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Reconstruction of Gaussian quantum mechanics from Liouville mechanics with an epistemic restriction
• Stabilizer states and Clifford operations for systems of arbitrary dimensions, and modular arithmetic
• Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Qudit versions of the qubit "pi-over-eight" gate
• SIC~POVMs and Clifford groups in prime dimensions
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Simulation of low-depth quantum circuits as complex undirected graphical models
• Properties of the extended Clifford group with applications to SIC-POVMs and MUBs
• Discrete Wigner Formalism for Qubits and Non-Contextuality of Clifford Gates on Qubit Stabilizer States
• Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond
• Maximum nonlocality and minimum uncertainty using magic states
• Efficient Inner-product Algorithm for Stabilizer States
• Measurement Contextuality and Planck's Constant
• The Non-Disjoint Ontic States of the Grassmann Ontological Model, Transformation Contextuality, and the Single Qubit Stabilizer Subtheory

Cited by in corpus (12)

• Stim: a fast stabilizer circuit simulator
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• The Fermionic Quantum Emulator
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Improved Simulation of Quantum Circuits by Fewer Gaussian Eliminations
• Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Improved Strong Simulation of Universal Quantum Circuits
• Qudit Noisy Stabilizer Formalism