We consider a model of quantum computation using qubits where it is possible to measure whether a given pair are in a singlet (total spin 0 ) or triplet (total spin 1 ) state. The physical motivation is that we can do these measurements in a way that is protected against revealing other information so long as all terms in the Hamiltonian are SU(2) -invariant. We conjecture that this model is equivalent to BQP. Towards this goal, we show: (1) this model is capable of universal quantum computation with polylogarithmic overhead if it is supplemented by single qubit X and Z gates. (2) Without any additional gates, it is at least as powerful as the weak model of "permutational quantum computation" of Jordan [14, 18]. (3) With postselection, the model is equivalent to PostBQP.
We consider a model of quantum computation using qubits where it is possible to measure whether a given pair are in a singlet (total spin 0 ) or triplet (total spin 1 ) state. The physical motivation is that we can do these measurements in a way that is protected against revealing other information so long as all terms in the Hamiltonian are SU(2) -invariant. We conjecture that this model is equivalent to BQP. Towards this goal, we show: (1) this model is capable of universal quantum computation with polylogarithmic overhead if it is supplemented by single qubit X and Z gates. (2) Without any additional gates, it is at least as powerful as the weak model of "permutational quantum computation" of Jordan [14, 18]. (3) With postselection, the model is equivalent to PostBQP.
Abstract In order to delineate which minimalistic physical primitives can enable the full power of universal quantum computing, it has been fruitful to consider various measurement based architectures which reduce or eliminate the use of coherent unitary evolution, and also involve operations that are physically natural. In this context previous works had shown that the triplet-singlet measurement of two qubit angular momentum (or equivalently two qubit exchange symmetry) yields the power of quantum computation given access to a few additional different single qubit states or gates. However, Freedman, Hastings and Shokrian-Zini1 recently proposed a remarkable conjecture, called the ‘STP=BQP’ conjecture, which states that the two-qubit singlet/triplet measurement is quantum computationally universal given only an initial ensemble of maximally mixed single qubits. In this work we prove this conjecture. This provides a method for quantum computing that is fully rotationally symmetric (i.e. reference frame independent), using primitives that are physically very-accessible, naturally resilient to certain forms of error, and provably the simplest possible.
We prove that universal quantum computation is possible using only (i) the physically natural measurement on two qubits which distinguishes the singlet from the triplet subspace and (ii) qubits prepared in almost any three different (potentially highly mixed) states. In some sense this measurement is a 'more universal' dynamical element than a universal two-qubit unitary gate, since the latter must be supplemented by measurement. Because of the rotational invariance of the measurement used, our scheme is robust to collective decoherence in a manner very different to previous proposals—in effect it is only ever sensitive to the relational properties of the qubits.
Joint measurements of two-Pauli observables are powerful tools for both the control and protection of quantum information. By following a simple recipe for measurement choices, single- and two- qubit rotations using two-Pauli parity and single qubit measurements are guaranteed to be unitary while requiring only a single ancilla qubit. This language for measurement based quantum computing is shown to be directly applicable to encoded double quantum dot singlet-triplet spin qubits, by measuring spin-parity between dots from neighboring qubits. Along with exchange interaction, a complete, leakage free, measurement based gate set can be shown, up to a known Pauli correction. Both theoretically exact spin-parity measurements and experimentally demonstrated asymmetric spin-parity measurements are shown to be viable for achieving the proposed measurement based scheme, provided some extra leakage mitigating measurement steps. This method of spin qubit control offers a leakage suppressed, low resource overhead implementation of a measurement-based control that is viable on current spin qubit processor devices.
We introduce Exchange Quantum Polynomial Time (XQP) circuits, which comprise quantum computation using only computational basis SPAM and the isotropic Heisenberg exchange interaction. Structurally, this restricted model captures decoherence-free subspace computation without access to singlet states. We prove that XQP, as well as its constrained family consisting solely of SWAP gates, is universal for quantum computation under polynomial overheads in circuit depth and size. This establishes the universality of the SWAP gate on its own under a logical encoding of qubits. We further prove that circuits generated by SWAP gates are semi-universal, and thus generate t-designs for the uniform distribution over SU(2)-invariant unitaries. Finally, we study additional properties of the XQP model, including its relation to the six-vertex and Potts model in statistical physics. Our findings suggest that XQP circuits are naturally suited to near-term hardware and provide a simple platform for experimental demonstrations of quantum advantage.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers. The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected. This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate. Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
We consider ground states of quantum spin chains with symmetry-protected topological (SPT) order as resources for measurement-based quantum computation (MBQC). We show that, for a wide range of SPT phases, the computational power of ground states is uniform throughout each phase. This computational power, defined as the Lie group of executable gates in MBQC, is determined by the same algebraic information that labels the SPT phase itself. We prove that these Lie groups always contain a full set of single-qubit gates, thereby affirming the long-standing conjecture that general SPT phases can serve as computationally useful phases of matter.