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)- Constant-optimized quantum circuits for modular multiplication and exponentiation
- Quantum circuit oracles for abstract machine computations
- Efficient quantum circuit of Proth number modular multiplication
- Classical and Quantum Algorithms for Exponential Congruences
- Evolving quantum circuits at the gate level with a hybrid quantum-inspired evolutionary algorithm
- An \(R||C_{\max}\) quantum scheduling algorithm
- On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
- Practical security of RSA against NTC-architecture quantum computing attacks
- Quantum plug n' play: modular computation in the quantum regime
- Truncated modular exponentiation operators: a strategy for quantum factoring
- Space-efficient and noise-robust quantum factoring
- On the various ways of quantum implementation of the modular exponentiation function for Shor's factorization
- Emulation of high-performance correlation-based quantum clustering algorithm for two-dimensional data on FPGA
- Quantum arithmetic with the quantum Fourier transform
- Construction and optimization of quantum modular exponentiation circuits based on the V gate
- Circuit design for a measurement-based quantum carry-lookahead adder
- An implementation of quantum oracles for the finite element method
- Faster quantum chemistry simulation on fault-tolerant quantum computers
- Architecture of a Quantum Multicomputer Implementing Shor’s Algorithm
- Quantum attacks on pseudorandom generators
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)
