In parity quantum computing, multiqubit logical gates are implemented by single-qubit rotations on a suitably encoded state involving auxiliary qubits. Consequently, there is a correspondence between qubit count and the size of the native gate set. One might then wonder, what is the smallest number of auxiliary qubits that still allows for universal parity computing? Here, we demonstrate that the answer is 1 if the number of logical qubits is even, and 2 otherwise. Furthermore, we present a sufficient condition for a given parity gate set to be universal. This leads to a variety of different universal parity gate sets corresponding to different numbers of auxiliary qubits and more generally contributes to the understanding of which entangling gates are required to augment the set of single-qubit unitaries to perform universal quantum computing. As a consequence, we obtain (i) minimal implementations of the parity framework on, e.g., a triangular lattice, (ii) hardware-specific implementations of the parity flow framework on, e.g., a heavy-hex lattice, and (iii) novel universal resources for measurement-based quantum computation.
In parity quantum computing, multiqubit logical gates are implemented by single-qubit rotations on a suitably encoded state involving auxiliary qubits. Consequently, there is a correspondence between qubit count and the size of the native gate set. One might then wonder, what is the smallest number of auxiliary qubits that still allows for universal parity computing? Here, we demonstrate that the answer is 1 if the number of logical qubits is even, and 2 otherwise. Furthermore, we present a sufficient condition for a given parity gate set to be universal. This leads to a variety of different universal parity gate sets corresponding to different numbers of auxiliary qubits and more generally contributes to the understanding of which entangling gates are required to augment the set of single-qubit unitaries to perform universal quantum computing. As a consequence, we obtain (i) minimal implementations of the parity framework on, e.g., a triangular lattice, (ii) hardware-specific implementations of the parity flow framework on, e.g., a heavy-hex lattice, and (iii) novel universal resources for measurement-based quantum computation.
We propose a universal gate set for quantum computing with all-to-all connectivity and intrinsic robustness to bit-flip errors based on parity encoding. We show that logical controlled phase gate and R_{z} rotations can be implemented in parity encoding with single-qubit operations. Together with logical R_{x} rotations, implemented via nearest-neighbor controlled-NOT gates and an R_{x} rotation, these form a universal gate set. As the controlled phase gate requires only single-qubit rotations, the proposed scheme has advantages for several cornerstone quantum algorithms, e.g., the quantum Fourier transform. We present a method to switch between different encoding variants via partial on-the-fly encoding and decoding.
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 demonstrate the applicability of a universal gate set in the parity encoding, which is a dual to the standard gate model, by exploring several quantum gate algorithms such as the quantum Fourier transform and quantum addition. Embedding these algorithms in the parity encoding reduces the circuit depth compared to conventional gate-based implementations while keeping the multiqubit gate counts comparable. We further propose simple implementations of multiqubit gates in tailored encodings and an efficient strategy to prepare graph states.
One of the main challenges the implementation of quantum optimization algorithms has been facing in the last year is the connectivity of qubits on quantum chips. The parity architecture has emerged as an approach to address this issue by trading qubit connectivity for an overhead in the number of physical qubits by encoding the parity of logical qubits. This qubit overhead comes with so-called parity constraints that can be implemented geometrically locally on the quantum chip. While the parity architecture is suitable for both analog and digital quantum computing, we focus on the digital side in this thesis, and present new insights on the parity approach from two perspectives. First, we investigate its resource requirements for quantum optimization, in particular for the Quantum Approximate Optimization Algorithm (QAOA), and propose a constructive algorithm to reduce these requirements compared to previous strategies. In addition, by viewing the parity constraints as stabilizers, we introduce a strategy to conserve the parity constraints throughout the execution of the QAOA. This is in contrast to previous work on the parity architecture, where the parity constraints were typically enforced via additional energy penalties. Second, we show how the parity framework can be used for universal quantum computation, and how cornerstone algorithms like the quantum Fourier transform benefit from this new approach. Our method essentially allows to trade a high circuit-depth for a qubit overhead, while at the same time offering more flexibility in circuit design by enabling on-the-fly recoding of physical qubits. Furthermore, we present a universal quantum computing approach in the parity architecture based on quantum measurements, which allows for additional reductions in circuit depth. Finally, we outline how the parity architecture can be exploited for quantum error correction. With these findings, we aim to contribute to building the bridge between the current era of non-error-corrected hardware and fault-tolerant quantum computing.
Implementing a qubit quantum computer in continuous-variable systems conventionally requires the engineering of specific interactions according to the encoding basis states. In this work, we present a unified formalism to conduct universal quantum computation with a fixed set of operations but arbitrary encoding. By storing a qubit in the parity of two or four qumodes, all computing processes can be implemented by basis state preparations, continuous-variable exponential-swap operations, and swap tests. Our formalism inherits the advantages that the quantum information is decoupled from collective noise, and logical qubits with different encodings can be brought to interact without decoding. We also propose a possible implementation of the required operations by using interactions that are available in a variety of continuous-variable systems. Our work separates the "hardware" problem of engineering quantum-computing-universal interactions, from the "software" problem of designing encodings for specific purposes. The development of quantum computer architecture could hence be simplified.
We study the resources required to achieve universal quantum computing via the gate sets that provide the fundamental instructions from which quantum algorithms are built. While single-gate universal sets are known, they rely on precisely tuned irrational rotations, making them difficult to realize on near-term devices. We find that the controlled-V gate, an elementary two-qubit interaction directly implementable on leading hardware, is universal and capable of simulating standard universal gate sets with minimal overhead. Specifically, we use catalytic embeddings to develop a constant-overhead algorithm that simulates standard universal gate sets, including Clifford+T and Clifford+Toffoli. We combine this simulation algorithm with existing synthesis results to yield exact and approximate synthesis algorithms for unitaries with and without number-theoretic restrictions. The results highlight how full quantum computational power, complete with algorithms for synthesis and simulation, can emerge from unexpectedly simple ingredients.