The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform

• URL: http://arxiv.org/abs/2409.02506v1
• Date: Wed, 4 Sep 2024 08:06:11 GMT
• Title: The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform
• Authors: Qiqing Xia, Huiqin Xie, Li Yang,
• Abstract summary: We study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.
• Score: 9.657072841833243
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-$R_k$ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-$R_k$ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.

Related papers

• 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)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• A fault-tolerant variational quantum algorithm with limited T-depth [2.7648976108201815]
  We propose a variational quantum eigensolver (VQE) algorithm that uses a fault-tolerant gate-set. VQE is suitable for implementation on a future error-corrected quantum computer.
  arXiv  Detail & Related papers  (2023-03-08T10:31:12Z)
• Direct pulse-level compilation of arbitrary quantum logic gates on superconducting qutrits [36.30869856057226]
  We demonstrate any arbitrary qubit and qutrit gate can be realized with high-fidelity, which can significantly reduce the length of a gate sequence. We show that optimal control gates are robust to drift for at least three hours and that the same calibration parameters can be used for all implemented gates.
  arXiv  Detail & Related papers  (2023-03-07T22:15:43Z)
• Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
  We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
  arXiv  Detail & Related papers  (2022-09-30T02:36:42Z)
• Error Mitigation-Aided Optimization of Parameterized Quantum Circuits: Convergence Analysis [42.275148861039895]
  Variational quantum algorithms (VQAs) offer the most promising path to obtaining quantum advantages via noisy processors. gate noise due to imperfections and decoherence affects the gradient estimates by introducing a bias. Quantum error mitigation (QEM) techniques can reduce the estimation bias without requiring any increase in the number of qubits. QEM can reduce the number of required iterations, but only as long as the quantum noise level is sufficiently small.
  arXiv  Detail & Related papers  (2022-09-23T10:48:04Z)
• Optimizing the number of CNOT gates in one-dimensional nearest-neighbor quantum Fourier transform circuit [0.0]
  We construct a one-dimensional nearest-neighbor circuit of quantum Fourier transform (QFT) It is found that our method reduces the number of CNOT gates by 60%. Our results for the one-dimensional nearest-neighbor circuit can be applied to quantum amplitude estimation.
  arXiv  Detail & Related papers  (2022-08-30T13:24:16Z)
• T-count optimization of approximate quantum Fourier transform [0.0]
  We present a new n-qubit QFT circuit approximated to error O(varepsilon) using Toffoli gates and quantum adders.
  arXiv  Detail & Related papers  (2022-03-15T09:13:51Z)
• Software mitigation of coherent two-qubit gate errors [55.878249096379804]
  Two-qubit gates are important components of quantum computing. But unwanted interactions between qubits (so-called parasitic gates) can degrade the performance of quantum applications. We present two software methods to mitigate parasitic two-qubit gate errors.
  arXiv  Detail & Related papers  (2021-11-08T17:37:27Z)
• Approaching the theoretical limit in quantum gate decomposition [0.0]
  We propose a novel numerical approach to decompose general quantum programs in terms of single- and two-qubit quantum gates with a $CNOT$ gate count. Our approach is based on a sequential optimization of parameters related to the single-qubit rotation gates involved in a pre-designed quantum circuit used for the decomposition.
  arXiv  Detail & Related papers  (2021-09-14T15:36:22Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.