Source-linked AI summary
Matchgates and classical simulation of quantum circuits
Richard Jozsa, Akimasa Miyake
TL;DR
The paper asks where the boundary lies between classically simulatable and quantum computationally powerful circuits built from parity-preserving two-qubit gates. Using Clifford algebras and the Jordan-Wigner representation, it proves efficient simulation for nearest-neighbour circuits and extends simulation to Gaussian circuits, while next-nearest-neighbour access enables universal computation.
Problem
The paper investigates the boundary between efficient classical simulation and quantum computational power for circuits of parity-preserving G(A, B) gates.
Method
It uses a Clifford-algebra formalism together with Clifford operations and the Jordan-Wigner representation to analyze matchgate and Gaussian circuits.
Results
Nearest-neighbour G(A, B) circuits are classically efficiently simulatable, whereas allowing nearest- and next-nearest-neighbour gates suffices for universal quantum computation.
Takeaways & Limitations
A one-step extension of the interaction range bridges the paper’s classical-simulation and universal-computation regimes.
Takeaways & Limitations
The simulation definition requires computing measurement probabilities to m digits of accuracy in poly(n, m) time, a stronger criterion than inverse-polynomial accuracy or sampling.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies when matchgate circuits can be classically simulated and how a small relaxation of nearest-neighbour locality changes their computational power. It introduces a Clifford-algebra approach, establishes simulation for nearest-neighbour circuits, and develops Gaussian-circuit generalizations.
- Matchgate circuits: G(A, B) applies A to the even-parity subspace and B to the odd-parity subspace, with both gates in SU(2) or same-determinant U(2).
- Nearest-neighbour simulation: Theorem 1 classically efficiently simulates uniform nearest-neighbour G(A, B) circuits with arbitrary product-state inputs and a single computational-basis output measurement.The simulation computes the expectation value of Z_k, equivalently the difference between the two output probabilities.
- Simulation criterion: The paper defines efficient classical simulation as computing measurement probabilities to m digits of accuracy in poly(n, m) time.
- Simulation criterion: The adopted simulation notion is stronger than inverse-polynomial-accuracy computation or one-time classical sampling of the output distribution.
- Locality relaxation: Allowing G(A, B) gates on next-nearest-neighbour lines yields universal quantum computation with only a modest extension of the nearest-neighbour interaction range.
- Generalizations: The Clifford-algebra treatment further identifies a uniformly describable simulatable gate family and extends the framework to Gaussian quantum circuits.
2 Universality of n.n. and next-n.n. G(A, B) gates
Nearest-neighbour G(A,B) circuits can be classically simulated, but allowing next-nearest-neighbour interactions suffices to simulate arbitrary quantum circuits with only constant size overhead. This modest relaxation is implemented through encoded logical gates and limited qubit swapping.
- Universality: Nearest-neighbour G(A,B) gates together with SWAP, or equivalently arbitrary pair interactions, can perform universal quantum computation.The nearest-neighbour restriction is therefore essential to the classical simulation result.
- Universality: Any uniform circuit with a computational-basis Z measurement can be simulated using G(A,B) gates on nearest- or next-nearest-neighbour lines.The construction uses line pairs at distance at most 2 and increases circuit size by at most a constant factor.
- Role of SWAP: SWAP on nearest-neighbour lines bridges the classical and quantum regimes by allowing nearest-neighbour gates to act one line farther apart.The paper identifies this as a very limited use of an otherwise seemingly innocuous operation.
- Role of SWAP: SWAP is nearly an allowed G(A,B) gate: SWAP = ˜G(I, X), differing only because det X ≠ det I.Dropping the equal-determinant condition makes nearest-neighbour ˜G(A,B) gates efficiently universal.
- Encoded construction: The encoding uses consecutive quadruples so commuting crossover SWAPs moves each line by at most one position and yields interactions no farther than next-nearest neighbours.A final measurement on line 1 reproduces the original circuit’s output distribution.
- Encoded construction: Using the simpler encoding |0L⟩ = |00⟩ and |1L⟩ = |11⟩ would require G(A,B) gates on lines up to distance 3.The quadruple encoding keeps the interaction range at distance 2.
3 Perfect matchings and matchgates
Matchgates connect quantum circuit simulation with polynomial-time algorithms for perfect matchings. Their tensor-network contractions correspond to match sums, and unitary instances include the G(A,B) gates studied in the paper.
- Origins: Matchgates originated in Valiant’s work on perfect matchings, whose counting problem is computationally hard.The matchgate formalism translates suitable graph problems into tensor descriptions used in quantum circuits.
- Tensor construction: Graph tensors with designated input and output vertices have components computable in polynomial time by applying the FKT algorithm after deleting indexed vertices.Each tensor component corresponds to a graph obtained by selecting input and output indices.
- Tensor construction: Matchgate circuits represent contractions of matchgate tensor networks, which correspond to evaluating the match sum of a combined graph.This provides the graph-theoretic basis for classical simulation.
- Quantum circuits: Some matchgate tensors are unitary, yielding quantum circuits that can be classically efficiently simulated.The gates G(A,B) arise as unitary matchgates with two input and two output vertices.
- Perfect matchings: The FKT algorithm computes the Pfaffian of an antisymmetric incidence matrix in polynomial time, despite the Pfaffian’s exponentially large formal expansion.For planar weighted graphs, this also gives a polynomial-time computation of the match sum.
4 Clifford algebras, quadratic Hamiltonians and classical simulation
The paper uses Clifford algebras and quadratic Hamiltonians to represent Gaussian operations whose conjugation acts linearly on Majorana generators. This polynomial-size representation enables efficient simulation for product inputs and suitably low-degree observables.
- Clifford algebra: The Clifford algebra C2n is generated by 2n Hermitian operators satisfying {cµ,cν} = 2δµνI.Its elements are linear combinations of generator monomials, and the algebra has dimension 2^2n.
- Scope: The paper treats Clifford-algebra-based circuit simulation rather than free fermions alone, and notes that the 2n+1-generator extension gives no significant generalization.This marks both the broader intended scope and a stated boundary of the algebraic extension.
- Gaussian operations: Quadratic Hamiltonians are real antisymmetric combinations of generator products, and their exponentials define Gaussian operations.The paper uses these operations as the algebraic basis for circuit simulation.
- Gaussian operations: Gaussian conjugation maps every generator linearly to a combination of generators through a matrix R in SO(2n), with R = e^4h.Although the unitary may contain exponentially many algebra terms, its adjoint action remains in a 2n-dimensional subspace.
- Classical simulation: The product of the SO(2n) matrices for individual gates is polynomial-time computable, enabling efficient propagation of generator expectations.For product-state inputs represented by product operators, the initial expectations are also polynomial-time computable.
- Classical simulation: A measured observable Zk is efficiently simulatable when it has a polynomial representation of degree d that does not grow with n.The corresponding expectation calculation has O(n^d) terms; for a quadratic representation, the sum is O(n^2).
5 The Jordan-Wigner representation and theorem 1
The Jordan-Wigner representation realizes the Clifford generators as product operators, making computational-basis observables low-degree polynomials and nearest-neighbour G(A,B) gates Gaussian. This representation supports efficient simulation and an exact polynomial-size decomposition of arbitrary Gaussian operations into nearest-neighbour G(A,B) gates.
- Jordan-Wigner representation: The Jordan-Wigner representation assigns two hermitian Clifford generators to each qubit line and represents them with Pauli strings.The generators satisfy the Clifford algebra relations, and each pair is associated with one qubit line.
- Jordan-Wigner representation: The observable Z_k equals -ic_2k−1c_2k, so its degree-two Clifford representation enables efficient expectation-value computation.The generators are product operators, and product-state inputs preserve the polynomial-time simulation strategy.
- Nearest-neighbour gates: Restricting quadratic Hamiltonians to the four generators associated with two consecutive lines yields precisely the nearest-neighbour G(A,B) gates.The six quadratic terms on two lines preserve even and odd parity and generate the two SU(2) actions.
- Nearest-neighbour gates: All nearest-neighbour G(A,B) gates are Gaussian in the Jordan-Wigner representation, completing the simulation proof for theorem 1.Gaussian operations preserve the relevant Clifford-algebra structure used to compute final Z_k expectations efficiently.
- Gaussian decomposition: Any Gaussian operation can be decomposed exactly into O(n^3) nearest-neighbour G(A,B) gates using rotations and modified-swap conjugations.The decomposition is analytic and explicitly describable in polynomial time; modified swaps exchange adjacent generator pairs and are themselves nearest-neighbour Gaussian gates.
- Gaussian decomposition: The same decomposition gives efficient digital simulation of one-dimensional systems whose Hamiltonians are quadratic, including the 1D XY Hamiltonian.The real-time dynamics can be simulated for any evolution time using nearest-neighbour G(A,B) gates.
6 Gaussian quantum circuits intertwined by Clifford operations
Clifford conjugations produce new Gaussian circuit families while preserving the algebraic structure needed for efficient simulation. Their locality and observable degree determine the resulting circuit scope and simulation cost, yielding examples of simulatable 3-local and 4-local gates.
- Intertwined Gaussian circuits: Conjugating the Clifford generators by a Clifford operation preserves their Pauli-product structure and can define new Gaussian circuits.The construction assumes the transformed observables retain bounded degree and the transformed gates remain suitably local.
- Intertwined Gaussian circuits: The transformed Gaussian gates equal the original Gaussian gates conjugated by T, while intermediate T and T† operations cancel between circuit layers.This gives an equivalent view of the new circuits as conjugated versions of the original simulatable circuits.
- Conditions for simulation: A global Clifford operation is useful only when transformed Z_k has bounded degree and the conjugated gates remain K-local for constant K.The simulation cost scales as O(n^d), where d is the degree of the observable polynomial.
- Generality of the construction: The construction can use Clifford operations whose structure varies with n and need not be translationally uniform, producing circuits with different gates on different line sections.The full nearest-neighbour G(A,B) gate set remains translationally uniform even when the chosen intertwining operation does not.
- Example 2: Example 2 produces a 15-parameter family of 3-local Gaussian gates, all obtainable from the initial six-parameter nearest-neighbour family and efficiently simulatable.The conjugated nearest-neighbour interactions become 3-local, while theorem 5 reduces the larger family back to circuits of the initial gates.
- Example 3: Example 3 yields a 13-parameter family of Gaussian gates on four consecutive lines from conjugated nearest-neighbour gates.Not all quadratic terms remain 4-local under the conjugation.
- Example 3: The associated 26-parameter family of 4-qubit gates remains classically efficiently simulatable, with simulation cost scaling as O(n^6).The higher cost follows from the sixth-degree Clifford monomial required for even-indexed Z_k observables.
7 Concluding remarks
The concluding discussion contrasts the complexity-theoretic implications of classically simulating nearest-neighbour versus next-nearest-neighbour circuits under PQP and BQP probability conditions. Under weaker sampling-based simulation, matching BPP and BQP would already follow.
- Probability conditions: BQP is defined using bounded output probabilities, while PQP relaxes these conditions to require only nonzero probabilities.The text identifies BQP as the bounded-probability setting and introduces PQP as its relaxed analogue.
- Complexity consequences: PQP contains BQP, NP, and PP, with PP = PQP.The inclusions and equality frame the stronger complexity-theoretic consequences considered for PQP circuits.
- Complexity consequences: Nearest-neighbour G(A,B) circuits form a class contained in P under the paper’s strong notion of classical simulation.This follows from Theorem 1’s efficient computation of output probabilities for nearest-neighbour circuits.
- Complexity consequences: If next-nearest-neighbour G(A,B) circuits were equally simulatable, then P = NP = PP would follow under PQP probability conditions.The single-distance extension therefore carries additional computational power unless those classical complexity classes coincide.
- BQP and weaker simulation: The same implication is less compelling under BQP conditions, while merely sampling the output once would suffice to obtain BPP = BQP.The text contrasts exponentially accurate probability computation with the weaker requirement of one classically efficient sample.