A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm

• URL: http://arxiv.org/abs/2503.10008v2
• Date: Thu, 20 Mar 2025 14:31:05 GMT
• Title: A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm
• Authors: Abu Musa Patoary, Amit Vikram, Victor Galitski,
• Abstract summary: We propose a quantum circuit for modular exponentiation.<n>The gate-complexity of our proposal is $O(L3)$ where L is the number of bits required to store the number being factorized.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is $O(L^3)$ where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized.

Related papers

• Optimizing Quantum Circuits via ZX Diagrams using Reinforcement Learning and Graph Neural Networks [38.499527873574436]
  We introduce a framework based on ZX calculus, graph-neural networks and reinforcement learning for quantum circuit optimization. By combining reinforcement learning and tree search, our method addresses the challenge of selecting optimal sequences of ZX calculus rewrite rules. We demonstrate our method's competetiveness with state-of-the-art circuit generalizations and capabilities on large sets of diverse random circuits.
  arXiv  Detail & Related papers  (2025-04-04T13:19:08Z)
• Provably optimal exact gate synthesis from a discrete gate set [0.0]
  We propose a method for exact circuit synthesizing using a discrete gate set. Our approach translates the problem of a gate specified by its unitary matrix into a satisfiability (SAT) instance.
  arXiv  Detail & Related papers  (2025-03-19T17:32:29Z)
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor [30.867632812964743]
  We experimentally demonstrate factoring of the integer with a trapped ion quantum processor using the Schnorr approach and a modified version of quantum approximate optimization algorithm (QAOA) We present experimental results on factoring $1591=37times43$ using 6 qubits as well as simulation results for $746579521times7817$ with 10 qubits and $35183361263263=4194191times8388593$ with 15 qubits.
  arXiv  Detail & Related papers  (2025-03-13T17:40:07Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
  arXiv  Detail & Related papers  (2025-02-24T16:59:16Z)
• Factoring an integer with three oscillators and a qubit [0.0]
  A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits.<n>Here we advocate an alternative approach centered on the physical setup and the associated set of available operations.<n>We show that these can be leveraged to great benefit by sidestepping the standard approach of reasoning about measurements in terms of individual qubits.
  arXiv  Detail & Related papers  (2024-12-17T18:43:18Z)
• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating optimal fits to data over finite fields, DQI achieves a better approximation ratio than any time known to us.<n>We demonstrate this by benchmarking on an instance with over 30,000 variables.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• An Efficient Quantum Factoring Algorithm [0.27195102129094995]
  We show that $n$bit integers can be factorized by independently running a quantum circuit with $tildeO(n3/2)$. The correctness of the algorithm relies on a number-theoretic assumption reminiscent of those used in subexponential classical factorization algorithms.
  arXiv  Detail & Related papers  (2023-08-12T13:57:38Z)
• Noisy Tensor Ring approximation for computing gradients of Variational Quantum Eigensolver for Combinatorial Optimization [33.12181620473604]
  Variational Quantum algorithms have established their potential to provide computational advantage in the realm of optimization. These algorithms suffer from classically intractable gradients limiting the scalability. This work proposes a classical gradient method which utilizes the parameter shift rule but computes the expected values from the circuits using a tensor ring approximation.
  arXiv  Detail & Related papers  (2023-07-08T03:14:28Z)
• Fourier-based quantum signal processing [0.0]
  Implementing general functions of operators is a powerful tool in quantum computation. Quantum signal processing is the state of the art for this aim. We present an algorithm for Hermitian-operator function design from an oracle given by the unitary evolution.
  arXiv  Detail & Related papers  (2022-06-06T18:02:30Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• 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)
• Quantum Compiling by Deep Reinforcement Learning [30.189226681406392]
  The architecture of circuital quantum computers requires layers devoted to compiling high-level quantum algorithms into lower-level circuits of quantum gates. The general problem of quantum compiling is to approximate any unitary transformation that describes the quantum computation, as a sequence of elements selected from a finite base of universal quantum gates. We exploit the deep reinforcement learning method as an alternative strategy, which has a significantly different trade-off between search time and exploitation time.
  arXiv  Detail & Related papers  (2021-05-31T15:32:15Z)
• 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.