Fast and effective techniques for T-count reduction via spider nest identities

• URL: http://arxiv.org/abs/2004.05164v2
• Date: Tue, 14 Apr 2020 21:50:31 GMT
• Title: Fast and effective techniques for T-count reduction via spider nest identities
• Authors: Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang
• Abstract summary: We describe techniques to reduce the T-count, based on the effective application of "spider nest identities" We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.
• Score: 0.27528170226206433
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and $\pi/2$-phase rotations, together with T operations ($\pi/4$-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [arXiv:1206.0758, 1303.2042, 1308.4134, 1601.07363, 1606.01904, 1701.00140] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [arXiv:1712.01557] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [arXiv:1601.07363]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of "spider nest identities": easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.

Related papers

• Efficient Differentiable Approximation of Generalized Low-rank Regularization [64.73416824444328]
  Low-rank regularization (LRR) has been widely applied in various machine learning tasks.<n>In this paper, we propose an efficient differentiable approximation of LRR.
  arXiv  Detail & Related papers  (2025-05-21T11:49:17Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Survival of the Optimized: An Evolutionary Approach to T-depth Reduction [2.089191490381739]
  We propose a Genetic Algorithm (GA)-based approach to discover near-optimal T-gate merge patterns across circuit layers. Our framework yields an average improvement of 1.2x across varying circuit sizes and T-gate densities.
  arXiv  Detail & Related papers  (2025-04-13T00:55:18Z)
• Low-overhead Magic State Circuits with Transversal CNOTs [0.0]
  This paper examines the implications of CNOTs on magic state preparation. We construct fault-tolerant circuits for CC, CS and T states with minimal T-depth and much lower CNOT and qubits.
  arXiv  Detail & Related papers  (2025-01-17T16:34:51Z)
• Reducing T-Count in quantum string matching algorithm using relative-phase Fredkin gate [0.0]
  This paper introduces the relative-phase Fredkin gate as a strategy to notably reduce the number of T gates (T-count) necessary for the QSM algorithm. We demonstrate our method is advantageous in terms of other circuit costs, such as the depth of T gates and the number of CNOT gates.
  arXiv  Detail & Related papers  (2024-11-02T15:27:18Z)
• Accelerating Error Correction Code Transformers [56.75773430667148]
  We introduce a novel acceleration method for transformer-based decoders. We achieve a 90% compression ratio and reduce arithmetic operation energy consumption by at least 224 times on modern hardware.
  arXiv  Detail & Related papers  (2024-10-08T11:07:55Z)
• High Precision Fault-Tolerant Quantum Circuit Synthesis by Diagonalization using Reinforcement Learning [0.8341988468339112]
  Empirical search-based synthesis methods can generate good implementations for a more extensive set of unitaries. We leverage search-based methods to reduce the general unitary synthesis problem to one of diagonal unitaries. On a subset of algorithms of interest for future term applications, diagonalization can reduce T gate counts by up to 16.8%.
  arXiv  Detail & Related papers  (2024-08-31T12:10:32Z)
• Correlated decoding of logical algorithms with transversal gates [3.6520503393751524]
  We show that logical algorithms can be substantially improved by decoding qubits jointly to account for error propagation during entangling gates. We numerically verify that this approach substantially reduces the space-time cost of deep logical Clifford circuits.
  arXiv  Detail & Related papers  (2024-03-05T19:13:32Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Robust Quantum Arithmetic Operations with Intermediate Qutrits in the NISQ-era [9.769081901589614]
  NISQ-era (Noisy Intermediate Scale Quantum) developments have raised the importance for quantum algorithms. In this paper, we introduce an intermediate qutrit method for efficient implementation of gate count and circuit-depth without T gate and ancilla. We demonstrate that the percentage decrease in the probability of error is significant due to the fact that we achieve circuit efficiency by reducing circuit-depth in comparison to qubit-only works.
  arXiv  Detail & Related papers  (2022-12-21T19:00:53Z)
• Softmax-free Linear Transformers [90.83157268265654]
  Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. Existing methods are either theoretically flawed or empirically ineffective for visual recognition. We propose a family of Softmax-Free Transformers (SOFT)
  arXiv  Detail & Related papers  (2022-07-05T03:08:27Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest. We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
  arXiv  Detail & Related papers  (2022-05-24T20:51:37Z)
• An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration [11.62834880315581]
  This paper presents a fast and accurate Frequent Directions algorithm named as r-BKIFD. The proposed r-BKIFD has a comparable error bound with original Frequent Directions, and the approximation error can be arbitrarily small when the number of iterations is chosen appropriately.
  arXiv  Detail & Related papers  (2021-09-24T01:36:42Z)

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.