A basic question in the theory of fault-tolerant quantum computation is to understand the fundamental resource costs for performing a universal logical set of gates on encoded qubits to arbitrary accuracy. Here we consider qubits encoded with constant space overhead (i.e. finite encoding rate) in the limit of arbitrarily large code distance d through the use of topological codes associated to triangulations of hyperbolic surfaces. We introduce explicit protocols to demonstrate how Dehn twists of the hyperbolic surface can be implemented on the code through constant depth unitary circuits, without increasing the space overhead. The circuit for a given Dehn twist consists of a permutation of physical qubits, followed by a constant depth local unitary circuit, where locality here is defined with respect to a hyperbolic metric that defines the code. Applying our results to the hyperbolic Fibonacci Turaev-Viro code implies the possibility of applying universal logical gate sets on encoded qubits through constant depth unitary circuits and with constant space overhead. Our circuits are inherently protected from errors as they map local operators to local operators while changing the size of their support by at most a constant factor; in the presence of noisy syndrome measurements, our results suggest the possibility of universal fault tolerant quantum computation with constant space overhead and time overhead of O ( d / log d ) . For quantum circuits that allow parallel gate operations, this yields the optimal scaling of space-time overhead known to date.
more »
« less
This content will become publicly available on August 16, 2024
A Converse for Fault-tolerant Quantum Computation
As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on space overhead? In this paper, we obtain a lower bound on the space overhead required for ϵ -accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on space overhead is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. The lower bound on space overhead obtained here leads to a strictly smaller upper bound on the noise threshold for noise that are not degradable. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d.
more »
« less
- Award ID(s):
- 2112890
- NSF-PAR ID:
- 10451555
- Date Published:
- Journal Name:
- Quantum
- Volume:
- 7
- ISSN:
- 2521-327X
- Page Range / eLocation ID:
- 1087
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract We study two-qubit circuits over the Clifford+CS gate set, which consists of the Clifford gates together with the controlled-phase gate CS = diag(1, 1, 1,
i ). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes through magic state distillation. Since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is often desirable to construct circuits that use few CS gates. In the present paper, we introduce an efficient and optimal synthesis algorithm for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operatorU and outputs a Clifford+CS circuit forU , which uses the least possible number of CS gates. Because the algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for that operator. We give an explicit description of these normal forms and use this description to derive a worst-case lower bound of$$5{{\rm{log}}}_{2}(\frac{1}{\epsilon })+O(1)$$ ϵ -approximate elements of SU(4). Our work leverages a wide variety of mathematical tools that may find further applications in the study of fault-tolerant quantum circuits. -
more » « less
Recent constructions of quantum low-density parity-check (QLDPC) codes provide optimal scaling of the number of logical qubits and the minimum distance in terms of the code length, thereby opening the door to fault-tolerant quantum systems with minimal resource overhead. However, the hardware path from nearest-neighbor-connection-based topological codes to long-range-interaction-demanding QLDPC codes is likely a challenging one. Given the practical difficulty in building a monolithic architecture for quantum systems, such as computers, based on optimal QLDPC codes, it is worth considering a distributed implementation of such codes over a network of interconnected medium-sized quantum processors. In such a setting, all syndrome measurements and logical operations must be performed through the use of high-fidelity shared entangled states between the processing nodes. Since probabilistic many-to-1 distillation schemes for purifying entanglement are inefficient, we investigate quantum error correction based entanglement purification in this work. Specifically, we employ QLDPC codes to distill GHZ states, as the resulting high-fidelity logical GHZ states can interact directly with the code used to perform distributed quantum computing (DQC), e.g. for fault-tolerant Steane syndrome extraction. This protocol is applicable beyond the application of DQC since entanglement distribution and purification is a quintessential task of any quantum network. We use the min-sum algorithm (MSA) based iterative decoder with a sequential schedule for distilling-qubit GHZ states using a ratefamily of lifted product QLDPC codes and obtain an input fidelity threshold ofunder i.i.d. single-qubit depolarizing noise. This represents the best threshold for a yield offor any GHZ purification protocol. Our results apply to larger size GHZ states as well, where we extend our technical result about a measurement property of-qubit GHZ states to construct a scalable GHZ purification protocol.
-
Quantum computers have recently made great strides and are on a long-term path towards useful fault-tolerant computation. A dominant overhead in fault-tolerant quantum computation is the production of high-fidelity encoded qubits, called magic states, which enable reliable error-corrected computation. We present the first detailed designs of hardware functional units that implement space-time optimized magic-state factories for surface code error-corrected machines. Interactions among distant qubits require surface code braids (physical pathways on chip) which must be routed. Magic-state factories are circuits comprised of a complex set of braids that is more difficult to route than quantum circuits considered in previous work [1]. This paper explores the impact of scheduling techniques, such as gate reordering and qubit renaming, and we propose two novel mapping techniques: braid repulsion and dipole moment braid rotation. We combine these techniques with graph partitioning and community detection algorithms, and further introduce a stitching algorithm for mapping subgraphs onto a physical machine. Our results show a factor of 5.64 reduction in space-time volume compared to the best-known previous designs for magic-state factories.more » « less
-
Measurement-based quantum computing (MBQC) is an alternative model of quantum computation that is equivalent to the standard gate-based model and is the preferred approach for several optical quantum computing architectures. In MBQC, a quantum computation is executed by preparing an entangled cluster state and then selectively measuring qubits. MBQC can be made fault-tolerant by creating an MBQC computation that executes the standard surface code, an approach known as "foliation." Recent results on gate-based quantum computing have demonstrated that in the presence of biased noise, a modified version of the surface code known as the XZZX code has much higher thresholds than the standard surface code. However, naively foliating the XZZX code does not result in a high-threshold fault-tolerant MBQC, because the foliation procedure does not preserve the noise bias of the physical qubits. To create a high-threshold fault-tolerant MBQC, we introduce a modified cluster state that preserves the bias, and use our modified cluster state to construct an MBQC computation that executes the XZZX code. Using full circuit-level noise simulations, we show that the threshold of our modified MBQC is higher than either the standard fault-tolerant MBQC or the naïve foliated XZZX code in the presence of biased noise, demonstrating the advantage of our approach.more » « less
