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.
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.
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.
We report the characterization of a universal set of logic gates for one-way quantum computing using a four-photon ‘star’ cluster state generated by fusing photons from two independent photonic crystal fibre sources. We obtain a fidelity for the cluster state of 0.66 ± 0.01 with respect to the ideal case. We perform quantum process tomography to completely characterize a controlled-NOT, Hadamard and T gate all on the same compact entangled resource. Together, these operations make up a universal set of gates such that arbitrary quantum logic can be efficiently constructed from combinations of them. We find process fidelities with respect to the ideal cases of 0.64 ± 0.01 for the CNOT, 0.67 ± 0.03 for the Hadamard and 0.76 ± 0.04 for the T gate. The characterization of these gates enables the simulation of larger protocols and algorithms. As a basic example, we simulate a Swap gate consisting of three concatenated CNOT gates. Our work provides some pragmatic insights into the prospects for building up to a fully scalable and fault-tolerant one-way quantum computer with photons in realistic conditions.
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.
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.
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
Let G ( A , B ) denote the two-qubit gate that acts as the one-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 allow 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 generalize the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.