Fast quantum modular exponentiation
From MaRDI portal
Abstract: We present a detailed analysis of the impact on modular exponentiation of architectural features and possible concurrent gate execution. Various arithmetic algorithms are evaluated for execution time, potential concurrency, and space tradeoffs. We find that, to exponentiate an n-bit number, for storage space 100n (twenty times the minimum 5n), we can execute modular exponentiation two hundred to seven hundred times faster than optimized versions of the basic algorithms, depending on architecture, for n=128. Addition on a neighbor-only architecture is limited to O(n) time when non-neighbor architectures can reach O(log n), demonstrating that physical characteristics of a computing device have an important impact on both real-world running time and asymptotic behavior. Our results will help guide experimental implementations of quantum algorithms and devices.
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- Parallel quantum computation and quantum codes
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Rapid solution of problems by quantum computation
Cited in
(20)- Quantum arithmetic with the quantum Fourier transform
- Efficient quantum circuit of Proth number modular multiplication
- Practical security of RSA against NTC-architecture quantum computing attacks
- An \(R||C_{\max}\) quantum scheduling algorithm
- Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA
- Circuit design for a measurement-based quantum carry-lookahead adder
- Constant-optimized quantum circuits for modular multiplication and exponentiation
- Quantum attacks on pseudorandom generators
- Faster quantum chemistry simulation on fault-tolerant quantum computers
- Classical and Quantum Algorithms for Exponential Congruences
- On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
- Architecture of a Quantum Multicomputer Implementing Shor’s Algorithm
- On the various ways of quantum implementation of the modular exponentiation function for Shor's factorization
- Quantum plug n' play: modular computation in the quantum regime
- Space-efficient and noise-robust quantum factoring
- Construction and optimization of quantum modular exponentiation circuits based on the V gate
- Truncated modular exponentiation operators: a strategy for quantum factoring
- An implementation of quantum oracles for the finite element method
- Evolving quantum circuits at the gate level with a hybrid quantum-inspired evolutionary algorithm
- Quantum circuit oracles for abstract machine computations
This page was built for publication: Fast quantum modular exponentiation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102391)
