Matchgates and classical simulation of quantum circuits
From MaRDI portal
Abstract: Let G(A,B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.
Recommendations
- Classical simulation of quantum circuits by half Gauss sums
- Classical simulation of Yang-Baxter gates
- Quantum matchgate computations and linear threshold gates
- Matchgate shadows for fermionic quantum simulation
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Revisiting the simulation of quantum Turing machines by quantum circuits
- Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
- Quantum Circuit Simulation
Cites work
- Dimer problem in statistical mechanics-an exact result
- Fermionic linear optics revisited
- Fermionic quantum computation
- Generalization of Euler Angles to N-Dimensional Orthogonal Matrices
- On the Power of Quantum Computation
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Rapid solution of problems by quantum computation
- Remarks on duality transformations and generalized stabilizer states
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
Cited in
(40)- Expressiveness of matchgates.
- Effective simulation of state distribution in qubit chains
- Quantum circuit approximations and entanglement renormalization for the Dirac field in \(1+1\) dimensions
- Classical simulation of quantum circuits by half Gauss sums
- Towards a multi target quantum computational logic
- Classically simulating quantum circuits with local depolarizing noise
- A matrix representation of quantum circuits over non-adjacent qudits
- Free fermions behind the disguise
- Tensors masquerading as matchgates: relaxing planarity restrictions on Pfaffian circuits
- The rational approximations of the unitary groups
- Universal computation with quantum fields
- Quantum matchgate computations and linear threshold gates
- Quantum Circuits That Can Be Simulated Classically in Polynomial Time
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- ANALYSIS OF AN EXPERIMENTAL QUANTUM LOGIC GATE BY COMPLEMENTARY CLASSICAL OPERATIONS
- Temporally unstructured quantum computation
- Compressing the hidden variable space of a qubit
- Matchgate and space-bounded quantum computations are equivalent
- Computing the Tutte polynomial of lattice path matroids using determinantal circuits
- A complete characterization of unitary quantum space
- scientific article; zbMATH DE number 7250161 (Why is no real title available?)
- Classical Ising model test for quantum circuits
- The power of noisy fermionic quantum computation
- Infrared-dressed entanglement of cold open-shell polar molecules for universal matchgate quantum computing
- A diagrammatic calculus of fermionic quantum circuits
- Invited Talk: Embedding Classical into Quantum Computation
- Clifford Algebras, Spin Groups and Qubit Trees
- Matchgate shadows for fermionic quantum simulation
- Commuting quantum circuits and complexity of Ising partition functions
- Clifford algebras, quantum neural networks and generalized quantum Fourier transform
- Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Brick wall quantum circuits with global fermionic symmetry
- Geometric representations of braid and Yang-Baxter gates
- Quantum algorithms for compositional text processing
- Displaced fermionic Gaussian states and their classical simulation
- Disorder-assisted error correction in Majorana chains
- Gaussianity and simulability of Cliffords and matchgates
- Characterization of non-adaptive Clifford channels
- Quantum circuits with free fermions in disguise
This page was built for publication: Matchgates and classical simulation of quantum circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3560332)
