We present a construction for circuits with low gate count and depth, implementing three- and four-body Pauli-Z product operators as they appear in the form of plaquette-shaped constraints in QAOA when using the parity mapping. The circuits can be implemented on any quantum device with nearest-neighbor connectivity on a square-lattice, using only one gate type and one orientation of two-qubit gates at a time. We find an upper bound for the circuit depth which is independent of the system size. The procedure is readily adjustable to hardware-specific restrictions, such as a minimum required spatial distance between simultaneously executed gates, or gates only being simultaneously executable within a subset of all the qubits, for example a single line.
We present a formalism based on tracking the flow of parity quantum information to implement algorithms on devices with limited connectivity without qubit overhead, SWAP operations, or shuttling. Instead, we leverage the fact that entangling gates not only manipulate quantum states but can also be exploited to transport quantum information. We demonstrate the effectiveness of this method by applying it to the quantum Fourier transform (QFT) and the quantum approximate optimization algorithm (QAOA) with n qubits. This improves upon all state-of-the-art implementations of the QFT on a linear nearest-neighbor architecture, resulting in a total circuit depth of 5 n − 3 and requiring n 2 − 1 gates. For the QAOA, our method outperforms SWAP networks, which are currently the most efficient implementation of the QAOA on a linear architecture. We further demonstrate the potential to balance qubit count against circuit depth by implementing the QAOA on twice the number of qubits using bilinear connectivity, which approximately halves the circuit depth.
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.
High-performance quantum low-density parity-check codes promise substantial reductions in the overhead of fault-tolerant quantum computation, but most constructions require long-range connectivity or qubit shuttling, both of which are difficult to realise in superconducting architectures. Here we introduce a family of quantum low-density parity-check codes that, for the first time, combines planar open-boundary layouts, finite-size advantages over surface codes, and syndrome extraction using only nearest-neighbour gates on a planar grid of qubits with either square or hexagonal connectivity. The resulting circuits achieve optimal constant-depth stabiliser measurement, independent of code size, and naturally remove leakage from the system by exchanging the roles of check and data qubits at each syndrome extraction round. We find finite-size instances such as a [[323,14,15]] code, whose code-efficiency ratio is nearly an order of magnitude larger than that of rotated surface-code patches. At around 40 circuit qubits per logical qubit, the best directional tile-code layouts reduce the per-logical per-round logical error rate by a factor of 100 relative to rotated surface-code memories. These results show that the advantages of quantum low-density parity-check codes can survive compilation into strictly planar nearest-neighbour circuits, bringing low-overhead fault-tolerant memories closer to near-term hardware.
We present a single framework to describe parity codes in exclusively spatial dimensions as quantum error correction codes, as well as parity codes with a temporal dimension, as quantum circuits. This framework builds on the stabilizer formalism to introduce label tracking of parity information for illustrating and constructing quantum circuits and quantum error correction codes. Additionally, this framework proposes the necessary transformations and conditions to translate between the spatial and temporal versions of a given parity code. This technique is then applied to find the temporal variant of the spatially extended LHZ-code [1] using CNOT gates on a linear nearest-neighbor (LNN) qubit architecture. The resulting quantum circuit provides an efficient implementation of quantum algorithms on LNN architectures, that require the interactions found in all-to-all connected transverse-field Ising models. Two widely used quantum algorithms that require such interactions are the Quantum Approximate Optimization Algorithm (QAOA) [2] and the quantum Fourier transform (QFT). For the QAOA, this is the first proposal with a linear circuit depth while not requiring more than
n2CNOT gates per iteration. Our approach for QFT, requiring only LNN connectivity, surpasses previous QFT implementations even on devices with high qubit connectivity in terms of circuit depth while not increasing the gate count in leading order.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant
δ>0, it
ε-approximates an arbitrary single-qubit gate using
O(log1+δ(1/ε)) clean ancillae, Hadamard and
T single-qubit gates,
O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard,
T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth
O(loglog(1/ε)), and we prove a matching
Ω(loglog(1/ε))-depth lower bound. Overall, we establish that
Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-
d QAC circuit can be simulated in depth
O(d) using only Hadamard,
X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity
∈/QAC
0 to proving a Parity lower bound against circuits consisting only of Hadamard,
X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.