CNOT-count optimized quantum circuit of the Shor's algorithm

• URL: http://arxiv.org/abs/2112.11358v1
• Date: Tue, 21 Dec 2021 16:56:22 GMT
• Title: CNOT-count optimized quantum circuit of the Shor's algorithm
• Authors: Xia Liu, Huan Yang and Li Yang
• Abstract summary: We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer.
• Score: 8.88308897530269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. While previous work mostly focuses on minimizing the number of qubits or the depth of circuit, we try to minimize the number of CNOT gate which primarily determines the running time on a ion trap quantum computer. First, we give the implementation of basic arithmetic with known lowest number of CNOT gate and the construction of improved modular exponentiation of a constant by accumulating intermediate date and windowing technique. Then, we precisely estimate the number of improved quantum circuit to perform Shor's algorithm for factoring a $n$-bit integer, which is $217\frac{n^3}{\log_2n}+4n^2+n$. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer. Finally, we discuss the lower bound of CNOT numbers needed to implement Shor's algorithm.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• 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)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits. The only qubits involved are the input and output registers themselves. Our algorithm has the potential to outperform previous problem sizes relevant in practice.
  arXiv  Detail & Related papers  (2024-03-26T18:00:03Z)
• 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)
• 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)
• Minimizing CNOT-count in quantum circuit of the extended Shor's algorithm for ECDLP [8.88308897530269]
  We analyze the feasibility of cracking ECDLP with improved quantum circuits using an ion trap quantum computer. We give precise quantum circuits for extended Shor's algorithm to calculate discrete logarithms on elliptic curves over prime fields. We analyze the running time and feasibility of the extended Shor's algorithm on an ion trap quantum computer according to the number of CNOTs.
  arXiv  Detail & Related papers  (2023-05-19T03:41:13Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Approximate encoding of quantum states using shallow circuits [0.0]
  A common requirement of quantum simulations and algorithms is the preparation of complex states through sequences of 2-qubit gates. Here, we aim at creating an approximate encoding of the target state using a limited number of gates. Our work offers a universal method to prepare target states using local gates and represents a significant improvement over known strategies.
  arXiv  Detail & Related papers  (2022-06-30T18:00:04Z)
• Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
  One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. We introduce the formalism of encoding so called semi-booleans, which allows convenient generation of unsigned integer arithmetic quantum circuits. We extend this type of evaluation with additional features, such as ancilla-free in-place multiplication and integer coefficient evaluation.
  arXiv  Detail & Related papers  (2021-12-20T14:00:36Z)
• 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)
• Improved quantum circuits for elliptic curve discrete logarithms [6.058525641792685]
  We present improved quantum circuits for elliptic curve scalar multiplication. We optimize low-level components such as reversible integer and modular arithmetic. We provide a full implementation of point addition in the Q# quantum programming language.
  arXiv  Detail & Related papers  (2020-01-27T04:08:49Z)

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.