Lower $T$-count with faster algorithms

• URL: http://arxiv.org/abs/2407.08695v1
• Date: Thu, 11 Jul 2024 17:31:20 GMT
• Title: Lower $T$-count with faster algorithms
• Authors: Vivien Vandaele,
• Abstract summary: We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times. We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated.
• Score: 3.129187821625805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Among the cost metrics characterizing a quantum circuit, the $T$-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the $T$-count reduction problem by proposing efficient $T$-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of $T$ gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated. We also prove that the number of $T$ gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of $n$ qubits is upper bounded by $n(n + 1)/2 + 1$, which is the best known upper bound achievable in polynomial time. From this we derive an upper bound of $(n + 1)(n + 2h)/2 + 1$ for the number of $T$ gates in a Clifford$+T$ circuit where $h$ is the number of internal Hadamard gates in the circuit, i.e.\ the number of Hadamard gates lying between the first and the last $T$ gate of the circuit.

Related papers

• Quantum hashing algorithm implementation [0.0]
  We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one.
  arXiv  Detail & Related papers  (2024-07-14T09:41:16Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  We improve Regev's recent quantum factoring algorithm (arXiv:2308.06572) We run our circuit independently $approx sqrtn$ times and applies Regev's classical postprocessing procedure. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors.
  arXiv  Detail & Related papers  (2023-10-02T04:31:21Z)
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates [40.56175933029223]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences [4.423586186569902]
  We propose an algorithm for synthesizing a sequence of $pi/4$ Pauli rotations with a minimal number of Hadamard gates. We present an algorithm which optimally minimizes the number of Hadamard gates lying between the first and the last $T$ gate of the circuit.
  arXiv  Detail & Related papers  (2023-02-14T13:44:11Z)
• Beyond Ans\"atze: Learning Quantum Circuits as Unitary Operators [30.5744362478158]
  We run gradient-based optimization in the Lie algebra $mathfrak u(2N)$. We argue that $U(2N)$ is not only more general than the search space induced by ansatz, but in ways easier to work with on classical computers.
  arXiv  Detail & Related papers  (2022-03-01T16:40:21Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Fast estimation of outcome probabilities for quantum circuits [0.0]
  We present two classical algorithms for the simulation of universal quantum circuits on $n$ qubits. Our algorithms complement each other by performing best in different parameter regimes. We provide a C+Python implementation of our algorithms and benchmark them using random circuits.
  arXiv  Detail & Related papers  (2021-01-28T19:00:04Z)
• A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
  This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes. We consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set.
  arXiv  Detail & Related papers  (2020-06-22T17:21:41Z)

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.