The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation

• URL: http://arxiv.org/abs/2311.12772v2
• Date: Mon, 8 Apr 2024 14:34:57 GMT
• Title: The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
• Authors: Charles Yuan, Michael Carbin,
• Abstract summary: Numerous quantum algorithms require the use of quantum error correction to overcome the unreliability of physical qubits. error correction imposes a performance bottleneck, known as T-complexity, that can make implementation of an algorithm run more slowly than on idealized hardware. We present a cost model that a developer can use to analyze the T-complexity of a program and pinpoint the sources of slowdown.
• Score: 10.655710695515044
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Numerous quantum algorithms require the use of quantum error correction to overcome the intrinsic unreliability of physical qubits. However, error correction imposes a unique performance bottleneck, known as T-complexity, that can make an implementation of an algorithm as a quantum program run more slowly than on idealized hardware. In this work, we identify that programming abstractions for control flow, such as the quantum if-statement, can introduce polynomial increases in the T-complexity of a program. If not mitigated, this slowdown can diminish the computational advantage of a quantum algorithm. To enable reasoning about the costs of control flow, we present a cost model that a developer can use to accurately analyze the T-complexity of a program and pinpoint the sources of slowdown. We also present a set of program-level optimizations, that a developer can use to rewrite a program to reduce its T-complexity, predict the T-complexity of the optimized program using the cost model, and then compile it to an efficient circuit via a straightforward strategy. We implement the program-level optimizations in Spire, an extension of the Tower quantum compiler. Using a set of 11 benchmark programs that use control flow, we show that the cost model is accurate, and that Spire's optimizations recover programs that are asymptotically efficient, meaning their runtime T-complexity under error correction is equal to their time complexity on idealized hardware. Our results show that optimizing a program before it is compiled to a circuit can yield better results than compiling the program to an inefficient circuit and then invoking a quantum circuit optimizer found in prior work. For our benchmarks, only 2 of 8 tested circuit optimizers recover circuits with asymptotically efficient T-complexity. Compared to these 2 optimizers, Spire uses 54x to 2400x less compile time.

Related papers

• Optimizing Quantum Circuits, Fast and Slow [7.543907169342984]
  We present a framework for thinking of rewriting and resynthesis as abstract circuit transformations. We then present a radically simple algorithm, GUOQ, for optimizing quantum circuits.
  arXiv  Detail & Related papers  (2024-11-06T18:34:35Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• Dependency-Aware Compilation for Surface Code Quantum Architectures [7.543907169342984]
  We study the problem of compiling quantum circuits for quantum computers implementing surface codes. We solve this problem efficiently and near-optimally with a novel algorithm. Our evaluation shows that our approach is powerful and flexible for compiling realistic workloads.
  arXiv  Detail & Related papers  (2023-11-29T19:36:19Z)
• Quantum Circuit Unoptimization [0.6449786007855248]
  We construct a quantum algorithmic primitive called quantum circuit unoptimization. It makes a given quantum circuit complex by introducing some redundancies while preserving circuit equivalence. We use quantum circuit unoptimization to generate compiler benchmarks and evaluate circuit optimization performance.
  arXiv  Detail & Related papers  (2023-11-07T08:38:18Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• Synthesizing Quantum-Circuit Optimizers [7.111661677477926]
  QUESO is an efficient approach for automatically synthesizing a quantum-circuit for a given quantum device. For an instance, in 1.2 minutes, QUESO can synthesize an correctness with high-probability guarantees.
  arXiv  Detail & Related papers  (2022-11-17T17:30:20Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization [0.14755786263360526]
  We explore which quantum algorithms for optimization might be most practical to try out on a small fault-tolerant quantum computer. Our results discourage the notion that any quantum optimization realizing only a quadratic speedup will achieve an advantage over classical algorithms.
  arXiv  Detail & Related papers  (2020-07-14T22:54:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.