Classical simulation of noninteracting-fermion quantum circuits

Abstract

We show that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant corresponds to a physical model of noninteracting fermions in one dimension. We give an alternative proof of his result using the language of fermions and extend the result to noninteracting fermions with arbitrary pairwise interactions, where gates can be conditioned on outcomes of complete von Neumann measurements in the computational basis on other fermionic modes in the circuit. This last result is in remarkable contrast with the case of noninteracting bosons where universal quantum computation can be achieved by allowing gates to be conditioned on classical bits (quant-ph/0006088).

26 pages, 1 figure, uses wick.sty; references added to recent results by E. Knill

References in corpus (4)

• Instantaneous non-local computation of low T-depth quantum circuits
• Quantum Algorithms for Fermionic Simulations
• Fermionic Linear Optics and Matchgates
• Encoded Universality in Physical Implementations of a Quantum Computer

Cited by in corpus (245)

• Variational Quantum Algorithms
• Efficient classical simulation of slightly entangled quantum computations
• Improved Simulation of Stabilizer Circuits
• On the role of entanglement in quantum computational speed-up
• Classical simulation of quantum many-body systems with a tree tensor network
• Simulating quantum computation by contracting tensor networks
• Universal computation by multi-particle quantum walk
• A Race Track Trapped-Ion Quantum Processor
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Information Scrambling in Computationally Complex Quantum Circuits
• Universal Quantum Computation with the nu=5/2 Fractional Quantum Hall State
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Matchgates and classical simulation of quantum circuits
• Charge detection enables free-electron quantum computation
• Quantum Logic Operations Using Single Photons and the Zeno Effect
• Quantum Computing Using Single Photons and the Zeno Effect
• Exponential Decay of Correlations Implies Area Law
• Fermionic partial tomography via classical shadows
• Quantum computing and the entanglement frontier
• Generalizations of entanglement based on coherent states and convex sets
• Symmetry enriched phases of quantum circuits
• An area law for entanglement from exponential decay of correlations
• Correcting coherent errors with surface codes
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Unitary circuits for strongly correlated fermions
• Majorana Fermion Codes
• Generalised Hong-Ou-Mandel Experiments with Bosons and Fermions
• Symmetry Principles in Quantum Systems Theory
• Complexity of quantum impurity problems
• A class of highly entangled many-body states that can be efficiently simulated
• On measurement-based quantum computation with the toric code states
• Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Resources for bosonic quantum computational advantage
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Qubits as Parafermions
• Fidelity witnesses for fermionic quantum simulations
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• Controlled-NOT for multiparticle qubits and topological quantum computation based on parity measurements
• Robustness of quantum memories based on Majorana zero modes
• Infrared-dressed entanglement of cold open-shell polar molecules for universal matchgate quantum computing
• qTorch: The Quantum Tensor Contraction Handler
• Entanglement structure of current-driven diffusive fermion systems
• From estimation of quantum probabilities to simulation of quantum circuits
• Dynamical phase transitions in sampling complexity
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Multipartite electronic entanglement purification with charge detection
• Entangling spins by measuring charge: a parity-gate toolbox
• Efficient polarization entanglement concentration for electrons with charge detection
• Quantum Entanglement in Second-quantized Condensed Matter Systems
• Cluster-state preparation and multipartite entanglement analyzer with fermions
• Stabilizing multiple topological fermions on a quantum computer
• Irreversible quantum evolution with quadratic generator: Review
• Free fermions behind the disguise
• Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Nonlocality and entanglement in measured critical quantum Ising chains
• Disorder-assisted error correction in Majorana chains
• Characterization of solvable spin models via graph invariants
• The Power of Noisy Fermionic Quantum Computation
• Fermionic Linear Optics Revisited
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Quantum Entropy and Central Limit Theorem
• Constant-Depth Circuits for Dynamic Simulations of Materials on Quantum Computers
• The quantum FFT can be classically simulated
• Proof of the absence of local conserved quantities in the XYZ chain with a magnetic field
• Measurement, control, and decay of quantum-dot spins
• Quantum algorithms for spin models and simulable gate sets for quantum computation
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• An entanglement perspective on the quantum approximate optimization algorithm
• Fast estimation of outcome probabilities for quantum circuits
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Matchgate and space-bounded quantum computations are equivalent
• Concatenated tensor network states
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• Extending matchgates into universal quantum computation
• Efficient classical algorithms for simulating symmetric quantum systems
• Generalized parity measurements
• Classical simulation of fermionic linear optics augmented with noisy ancillas
• Universal extensions of restricted classes of quantum operations
• Quantum machine learning with adaptive linear optics
• Approximation algorithms for quantum many-body problems
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation
• Crystalline Quantum Circuits
• Compressed quantum simulation of the Ising model
• How to simulate quantum measurement without computing marginals
• Universal measurement-based quantum computation in a one-dimensional architecture enabled by dual-unitary circuits
• An application benchmark for fermionic quantum simulations
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• The Fermionic Quantum Emulator
• Enhancement of thermal entanglement in two-qubit XY models
• Learning shallow quantum circuits
• Observing Floquet topological order by symmetry resolution
• Coherent errors and readout errors in the surface code
• Unwinding Short-Range Entanglement
• Error-mitigated fermionic classical shadows on noisy quantum devices
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Many-body Majorana braiding without an exponential Hilbert space
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• One-body entanglement as a quantum resource in fermionic systems
• Encoded Universality for Generalized Anisotropic Exchange Hamiltonians
• Classical simulation of non-Gaussian fermionic circuits
• Network coding for distributed quantum computation over cluster and butterfly networks
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Lie-algebraic classical simulations for quantum computing
• Solving search problems by strongly simulating quantum circuits
• Efficient simulation of quantum error correction under coherent error based on non-unitary free-fermionic formalism
• Mode-entanglement of Gaussian fermionic states
• Time Independent Universal Computing with Spin Chains: Quantum Plinko Machine
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Computational power of matchgates with supplementary resources
• Mixed-state quantum transport in correlated spin networks
• Classical Ising model test for quantum circuits
• Optimal Quench for Distance-Independent Entanglement and Maximal Block Entropy
• Unbiasing Fermionic Auxiliary-Field Quantum Monte Carlo with Matrix Product State Trial Wavefunctions
• From dual-unitary to biunitary: a 2-categorical model for exactly-solvable many-body quantum dynamics
• Error mitigation by training with fermionic linear optics
• The Learnability of Quantum States
• Power of one non-clean qubit
• Clifford algebras, Spin groups and qubit trees
• Geometries for universal quantum computation with matchgates
• Clifford recompilation for faster classical simulation of quantum circuits
• Error-correction and noise-decoherence thresholds for coherent errors in planar-graph surface codes
• Quantum matchgate computations and linear threshold gates
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• The Computational Complexity of Linear Optics
• Quantum-inspired permanent identities
• The principle of majorization: application to random quantum circuits
• Quantum Extensive Form Games
• Improved simulation of quantum circuits dominated by free fermionic operations
• Exactly solvable many-body dynamics from space-time duality
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• Compressed quantum metrology for the Ising Hamiltonian
• State exchange with quantum side information
• Phase space methods for Majorana fermions
• On non-completely positive quantum dynamical maps on spin chains
• Classical simulation of non-Gaussian bosonic circuits
• Protocols for classically training quantum generative models on probability distributions
• Free-fermion Page Curve: Canonical Typicality and Dynamical Emergence
• Classical simulation of quantum circuits by dynamical localization: analytic results for Pauli-observable scrambling in time-dependent disorder
• Fermionic Simulators for Enhanced Scalability of Variational Quantum Simulation
• Entanglement phase diagrams from partial transpose moments
• Efficient and practical Hamiltonian simulation from time-dependent product formulas
• Generalised state spaces and non-locality in fault tolerant quantum computing schemes
• Characterization of variational quantum algorithms using free fermions
• Complexity of full counting statistics of free quantum particles in product states
• Quantifying fermionic nonlinearity of quantum circuits
• The non-stabilizerness of fermionic Gaussian states
• Quantum Linear Optics via String Diagrams
• The computational power of normalizer circuits over black-box groups
• Faster Born probability estimation via gate merging and frame optimisation
• Compressed simulation of thermal and excited states of the 1-D XY-model
• Fermionic Magic Resources of Quantum Many-Body Systems
• Universal quantum computation with symmetric qubit clusters coupled to an environment
• Free-Fermion Subsystem Codes
• Quantum circuits with free fermions in disguise
• Quantum computation from fermionic anyons on a 1D lattice
• Computing quantum magic of state vectors
• Compressed variational quantum eigensolver for the Fermi-Hubbard model
• Sketching phase diagrams using low-depth variational quantum algorithms
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Hopf algebras and solvable unitary circuits
• Universal Quantum Computation by Scattering in the Fermi-Hubbard Model
• Navigating the noise-depth tradeoff in adiabatic quantum circuits
• Quantifying multiparticle entanglement with randomized measurements
• Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
• Measurement-based approach to entanglement generation in coupled quantum dots
• Robust Oscillations and Edge Modes in Nonunitary Floquet Systems
• The computational power of matchgates and the XY interaction on arbitrary graphs
• A rapidly mixing Markov chain from any gapped quantum many-body system
• Integrability of Goldilocks quantum cellular automata
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• A Simple and Efficient Joint Measurement Strategy for Estimating Fermionic Observables and Hamiltonians
• On the average-case complexity of learning output distributions of quantum circuits
• Computational Complexity of Some Quantum Theories in $1+1$ Dimensions
• Exact real time dynamics with free fermions in disguise
• Solving Free Fermion Problems on a Quantum Computer
• Matchgate circuits deeply thermalize
• Matchgate quantum computing and non-local process analysis
• Normalizer Circuits and Quantum Computation
• Geometric representations of braid and Yang-Baxter gates
• A Graph-Theoretic Framework for Free-Parafermion Solvability
• Reconstruction of Quantum Particle Statistics: Bosons, Fermions, and Transtatistics
• The matrix permanent and determinant from a spin system
• Quantum Circuits and Spin(3n) Groups
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Gaining confidence on the correct realization of arbitrary quantum computations
• Digital Quantum Simulation of Scalar Yukawa Coupling
• Permanents, Bosons and Linear Optics
• A diagrammatic calculus of fermionic quantum circuits
• Effect of dephasing on the current through a periodically driven quantum point contact
• Space-Efficient Error Reduction for Unitary Quantum Computations
• Classical simulation of dissipative fermionic linear optics
• Extracting the spin excitation spectrum of a fermionic system using a quantum processor
• Explicit Pfaffian Formula for Amplitudes of Fermionic Gaussian Pure States in Arbitrary Pauli Bases
• Relation between two measures of entanglement in spin-1/2 and spinless fermion quantum chain systems
• The Hilbert-space structure of free fermions in disguise
• Analyzing the free states of one quantum resource theory as resource states of another
• Majorana braiding simulations with projective measurements
• Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing
• Fermionic anyons: entanglement and quantum computation from a resource-theoretic perspective
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• The Sub-Exponential Critical Slowing Down at Floquet Time Crystal Phase Transition
• Effective simulation of state distribution in qubit chains
• Brick Wall Quantum Circuits with Global Fermionic Symmetry
• PAC-learning of free-fermionic states is NP-hard
• Classifying fermionic states via many-body correlation measures
• Efficient Eigenstate Preparation in an Integrable Model with Hilbert Space Fragmentation
• Characterizing maximally many-body entangled fermionic states by using $M$-body density matrix
• Non-Universality from Conserved Superoperators in Unitary Circuits
• Classical simulation of measurement-based quantum computation on higher-genus surface-code states
• Efficient multipartite entanglement concentration of electron-spin state with charge detection
• Characterization of non-adaptive Clifford channels
• Pinned QMA: The power of fixing a few qubits in proofs
• Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables
• Quantum Information Processing with Low-Dimensional Systems
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Equivalence of Stabilizer and Shannon Rényi Entropies: Exact Results for Quantum Critical Chains
• Clifford Gates in the Holant Framework
• Decoherence of Majorana zero modes mediated by gapless fermions
• Resource complexity of Symmetry Protected Topological phases
• Majorana string simulation of nonequilibrium dynamics in two-dimensional lattice fermion systems
• Quantum information and statistical mechanics: an introduction to frontier
• More global randomness from less-random local gates
• Mutual information in interacting spin systems
• Moments of Quantum Channel Ensembles
• Generalized Interference of Fermions and Bosons
• Comparing quantum complexity and quantum fidelity
• Dynamical complexity of non-Gaussian many-body systems with dissipation
• Hyperspheres and control of spin chains
• Efficient simulation of non-trivial dissipative spin chains via stochastic unraveling
• The symplectic rank of non-Gaussian quantum states
• On sampling determinantal and Pfaffian point processes on a quantum computer
• The Computational Power of Non-interacting Particles
• Cloud-Assisted Contracted Simulation of Quantum Chains
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Expanding the reach of quantum optimization with fermionic embeddings
• Effective non-local parity-dependent couplings in qubit chains