The computational power of matchgates and the XY interaction on arbitrary graphs
arXiv:1308.1463 · doi:10.26421/QIC14.11-12
Abstract
Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the qubits are arranged on certain other graphs. Here we characterize the power of matchgates acting on arbitrary graphs. Specifically, we show that they are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle. We also prove the same dichotomy for the XY interaction, a proper subset of matchgates related to some implementations of quantum computing.
arXiv comment10 pages, 6 figures
References in corpus (13)
- Universal Quantum Computation with the Exchange Interaction
- Classical simulation of noninteracting-fermion quantum circuits
- Charge detection enables free-electron quantum computation
- Entangled Bell and GHZ states of excitons in coupled quantum dots
- Indirect Interaction of Solid-State Qubits via Two-Dimensional Electron Gas
- Reducing Constraints on Quantum Computer Design by Encoded Selective Recoupling
- Fermionic Linear Optics and Matchgates
- Exact gate-sequences for universal quantum computation using the XY-interaction alone
- A 2 rebit gate universal for quantum computing
- Extending matchgates into universal quantum computation
- Compressed quantum simulation of the Ising model
- Compressed Simulation of evolutions of the XY-model
- Geometries for universal quantum computation with matchgates