In the circuit model, quantum computers rely on the availability of a universal quantum gate set. A particularly intriguing example is a set of two-qubit-only gates: 'matchgates', along with swap (the exchange of two qubits). In this paper, we show a simple decomposition of arbitrary matchgates into better-known elementary gates and implement a matchgate in a single-photon linear optics experiment. The gate performance is fully characterized via quantum process tomography. Moreover, we represent the resulting reconstructed quantum process in a novel way, as a fidelity map in the space of all possible non-local two-qubit unitaries. We propose the non-local distance —which is independent of local imperfections such as uncorrelated noise or uncompensated local rotations—as a new diagnostic process measure for the non-local properties of the implemented gate.
In the circuit model, quantum computers rely on the availability of a universal quantum gate set. A particularly intriguing example is a set of two-qubit-only gates: 'matchgates', along with swap (the exchange of two qubits). In this paper, we show a simple decomposition of arbitrary matchgates into better-known elementary gates and implement a matchgate in a single-photon linear optics experiment. The gate performance is fully characterized via quantum process tomography. Moreover, we represent the resulting reconstructed quantum process in a novel way, as a fidelity map in the space of all possible non-local two-qubit unitaries. We propose the non-local distance —which is independent of local imperfections such as uncorrelated noise or uncompensated local rotations—as a new diagnostic process measure for the non-local properties of the implemented gate.
An essential requirement for any quantum computing architecture is the existence of a universal set of quantum gates. Examples of such sets are the 2-qubit CNOT gate in combination with arbitrary 1-qubit gates, and the 3-qubit Toffoli gate together with the 1-qubit Hadamard. A third set, which has not been implemented so far, is Valiant's 2-qubit matchgate G(A,B) which is universal with the SWAP operation. This paper presents how symmetric Valiant gates are decomposed which are sufficient for universal quantum computation, using another universal class of gates - a controlled-Zthetasgate and single qubit unitaries. Various symmetric matchgates (G(H,H), G(X,X) and G(T,T)) in a two-photon experiment to build quantum logic gates using higher-dimensional Hilbert spaces are implemented. The gate operations are characterized via quantum process tomography.
Shortened abstract: In this thesis, I study two restricted models of quantum computing related to free identical particles. Free fermions correspond to a set of two-qubit gates known as matchgates. Matchgates are classically simulable when acting on nearest neighbors on a path, but universal for quantum computing when acting on distant qubits or when SWAP gates are available. I generalize these results in two ways. First, I show that SWAP is only one in a large family of gates that uplift matchgates to quantum universality. In fact, I show that the set of all matchgates plus any nonmatchgate parity-preserving two-qubit gate is universal, and interpret this fact in terms of local invariants of two-qubit gates. Second, I investigate the power of matchgates in arbitrary connectivity graphs, showing they are universal on any connected graph other than a path or a cycle, and classically simulable on a cycle. I also prove the same dichotomy for the XY interaction. Free bosons give rise to a model known as BosonSampling. BosonSampling consists of (i) preparing a Fock state of n photons, (ii) interfering these photons in an m-mode linear interferometer, and (iii) measuring the output in the Fock basis. Sampling approximately from the resulting distribution should be classically hard, under reasonable complexity assumptions. Here I show that exact BosonSampling remains hard even if the linear-optical circuit has constant depth. I also report several experiments where three-photon interference was observed in integrated interferometers of various sizes, providing some of the first implementations of BosonSampling in this regime. The experiments also focus on the bosonic bunching behavior and on validation of BosonSampling devices. This thesis contains descriptions of the numerical analyses done on the experimental data, omitted from the corresponding publications.
Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an n-qubit circuit containing N gates, m of which are universality-enabling gates and N−m of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed m as n→∞, the resource cost, T, scales as O((m+1en)2m+2). For m scaling as a linear function of n, however, T scale as O(22nH(nm+1)), where H(λ) is the binary entropy function.
Matchgates are a restricted set of two-qubit gates known to be classically simulable under particular conditions. Specifically, if a circuit consists only of nearest-neighbor matchgates, an efficient classical simulation is possible if either (i) the input is a computational-basis state and the simulation requires computing probabilities of multiqubit outcomes (including also adaptive measurements) or (ii) if the input is an arbitrary product state, but the output of the circuit consists of a single qubit. In this paper we extend these results to show that matchgates are classically simulable even in the most general combination of these settings, namely, if the inputs are arbitrary product states, if the measurements are over arbitrarily many output qubits, and if adaptive measurements are allowed. This remains true even for arbitrary single-qubit measurements, albeit only in a weaker notion of classical simulation. These results make for an interesting contrast with other restricted models of computation, such as Clifford circuits or (bosonic) linear optics, where the complexity of simulation varies greatly under similar modifications.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T gate (a T unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between n-qubit matchgate circuits and the standard representation of SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n) incurred in this smaller-dimensional representation translates at most into an O(nεSO(2n)) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XX Hamiltonian on n=4,8 qubits.
Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.