Quantum Networks for Elementary Arithmetic Operations

Abstract

Quantum computers require quantum arithmetic. We provide an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiation seems to be the most difficult (time and space consuming) part of Shor's quantum factorising algorithm. We show that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorised.

7 pages, LaTeX, + 6 PS figures in a tar compressed file. See also http://eve.physics.ox.ac.uk/QChome.html

References in corpus (2)

• Universality in Quantum Computation
• A Universal Two--Bit Gate for Quantum Computation

Cited by in corpus (215)

• Surface codes: Towards practical large-scale quantum computation
• Quantum Computing
• Reliable Quantum Computers
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Light fields in complex media: mesoscopic scattering meets wave control
• Information and Computation: Classical and Quantum Aspects
• Realization of a scalable Shor algorithm
• Substituting Quantum Entanglement for Communication
• Quantum Risk Analysis
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Efficient Networks for Quantum Factoring
• Natural two-qubit gate for quantum computation using the XY interaction
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Option Pricing using Quantum Computers
• Layered architecture for quantum computing
• Addition on a Quantum Computer
• Fast Quantum Modular Exponentiation
• Quantum algorithm and circuit design solving the Poisson equation
• Efficient fault-tolerant quantum computing
• Quantum arithmetic with the Quantum Fourier Transform
• Adding control to arbitrary unknown quantum operations
• Simulating chemistry efficiently on fault-tolerant quantum computers
• Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
• Decoherence and dissipation during a quantum XOR gate operation
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics
• Quantum information distributors: Quantum network for symmetric and asymmetric cloning in arbitrary dimension and continuous limit
• Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
• Decoherence limits to quantum computation using trapped ions
• Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
• Basic concepts in quantum computation
• Quantum Computation
• Variational Quantum Algorithms for Computational Fluid Dynamics
• Flexible resources for quantum metrology
• Quantum Robots and Environments
• Requirements for fault-tolerant factoring on an atom-optics quantum computer
• Oracles for Gauss's law on digital quantum computers
• Probabilistic implementation of universal quantum processors
• Design of Efficient Reversible Logic Based Binary and BCD Adder Circuits
• Efficient Quantum Transforms
• Exponential Gain in Quantum Computing of Quantum Chaos and Localization
• Quantum gate learning in engineered qubit networks: Toffoli gate with always-on interactions
• On the Role of Coherence in Shor's Algorithm
• Quantum Algorithms for Jet Clustering
• Single-particle digitization strategy for quantum computation of a ${\varphi }^4$ scalar field theory
• Factoring in a Dissipative Quantum Computer
• Creation of superposition of unknown quantum states
• Quantum Fourier Transform in Computational Basis
• Arithmetic on a Distributed-Memory Quantum Multicomputer
• Scalability of Shor's algorithm with a limited set of rotation gates
• Quantum Computing with black-box Subroutines
• Quantum computation with phase drift errors
• Quantum Fast Poisson Solver: the algorithm and modular circuit design
• $N$-body interactions between trapped ion qubits via spin-dependent squeezing
• Communication Links for Distributed Quantum Computation
• Recursive quantum repeater networks
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
• Demonstration of three- and four-body interactions between trapped-ion spins
• Novel Reversible TSG Gate and Its Application for Designing Components of Primitive Reversible/Quantum ALU
• Schumacher's quantum data compression as a quantum computation
• Quantum Multiplexing with the Orbital Angular Momentum of light
• Practical Quantum Computing: solving the wave equation using a quantum approach
• T-count optimization and Reed-Muller codes
• Quantum computing of delocalization in small-world networks
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• General-Purpose Parallel Simulator for Quantum Computing
• Quantum Carry-Save Arithmetic
• Fault-Tolerant Logical Gate Networks for CSS Codes
• Quantum Computing of Classical Chaos: Smile of the Arnold-Schrodinger Cat
• Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
• Programmable networks for quantum algorithms
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• A New Reversible TSG Gate and Its Application For Designing Efficient Adder Circuits
• Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
• Quantum arithmetic operations based on quantum Fourier transform on signed integers
• Reduction of Qubits in Quantum Algorithm for Monte Carlo Simulation by Pseudo-random Number Generator
• The Forbidden Quantum Adder
• Models of quantum computation and quantum programming languages
• Quantum circuit for the fast Fourier transform
• Quantum Differentially Private Sparse Regression Learning
• An $\Theta (\sqrt{n})$-depth Quantum Adder on a 2D NTC Quantum Computer Architecture
• Efficient quantum circuit for singular value thresholding
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Fault-tolerant Operations for Universal Blind Quantum Computation
• Toward scalable information processing with ultracold polar molecules in an electric field: a numerical investigation
• Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method
• High Performance Quantum Modular Multipliers
• The Quantum Fourier Transform and Extensions of the Abelian Hidden Subgroup Problem
• Fast optimization algorithms and the cosmological constant
• Entanglement Simulations of Shor's Algorithm
• Quantum algorithm for Neighborhood Preserving Embedding
• Reversible addition circuit using one ancillary bit with application to quantum computing
• Electric circuits for universal quantum gates and quantum Fourier transformation
• Scaling laws for Shor's algorithm with a banded quantum Fourier transform
• Robustness of QMA against witness noise
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• A quantum primality test with order finding
• Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder
• Implementing Shor's algorithm on Josephson Charge Qubits
• Continuous-Time Quantum Walks on Dynamic Graphs
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Towards an Automated Framework for Realizing Quantum Computing Solutions
• Quantum algorithm for credit valuation adjustments
• Improving performance of probabilistic programmable quantum processors
• Subsystem analysis of continuous-variable resource states
• Quantum Monte Carlo for Economics: Stress Testing and Macroeconomic Deep Learning
• Quantum Monte Carlo simulations for financial risk analytics: scenario generation for equity, rate, and credit risk factors
• On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
• Quantum Simulation of Second-Quantized Hamiltonians in Compact Encoding
• Tensor-product vs. geometric-product coding
• Entanglement-screening by nonlinear resonances
• Knapsack Problem variants of QAOA for battery revenue optimisation
• Shor's discrete logarithm quantum algorithm for elliptic curves
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Quantum Plain and Carry Look-Ahead Adders
• A high-fidelity method for a single-step $N$-bit Toffoli gate in trapped ions
• Towards Large-Scale Quantum Computation
• Logic Synthesis for Fault-Tolerant Quantum Computers
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Shor's factorization algorithm with a single control qubit and imperfections
• Quantum implementation of elementary arithmetic operations
• Tools for Quantum Algorithms
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• An Introduction to Quantum Computing for Non-Physicists
• Efficient realization of quantum primitives for Shor's algorithm using PennyLane library
• Non-Unitary Quantum Machine Learning
• Universal topological quantum computation with strongly correlated Majorana edge modes
• Applications of Universal Parity Quantum Computation
• Generalized measurements via programmable quantum processor
• The Representation of Natural Numbers in Quantum Mechanics
• Implementing fault-tolerant non-Clifford gates using the [[8,3,2]] color code
• Circuit for Shor's algorithm using 2n+3 qubits
• Quantum Computing of Poincare Recurrences and Periodic Orbits
• Resource-aware System Architecture Model for Implementation of Quantum aided Byzantine Agreement on Quantum Repeater Networks
• Effects of imperfections for Shor's factorization algorithm
• Optimized quantum implementation of elliptic curve arithmetic over binary fields
• Quantum Vertex Model for Reversible Classical Computing
• Multi-nucleon structure and dynamics via quantum computing
• Quantum Addition Circuits and Unbounded Fan-Out
• QRAM: A Survey and Critique
• Schrodinger cat animated on a quantum computer
• Optimal Estimation of States in Quantum Image Processing
• Towards Variational Quantum Algorithms for generalized linear and nonlinear transport phenomena
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Tensor network method for reversible classical computation
• A Quantum Computational Learning Algorithm
• Exploring Many-body Interactions Through Quantum Fisher Information
• Probing the limits of variational quantum algorithms for nonlinear ground states on real quantum hardware: The effects of noise
• Ancilla-free Quantum Adder with Sublinear Depth
• Quantum Computing and a Unified Approach to Fast Unitary Transforms
• Windowed quantum arithmetic
• Novel Reversible Multiplier Architecture Using Reversible TSG Gate
• Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits
• Ternary Logic Design in Topological Quantum Computing
• An example of use of Variational Methods in Quantum Machine Learning
• Minimizing CNOT-count in quantum circuit of the extended Shor's algorithm for ECDLP
• CNOT-count optimized quantum circuit of the Shor's algorithm
• Integer Arithmetic With Hybrid Quantum-Classical Circuits
• Partial Reversible Gates(PRG) for Reversible BCD Arithmetic
• Improved Quantum Ternary Arithmetics
• QHSL: a quantum hue, saturation, and lightness color model
• A quantum algorithm for solving systems of nonlinear algebraic equations
• Quantum search processes in the cyclic group state spaces
• Entanglement and its Role in Shor's Algorithm
• QFT based quantum arithmetic logic unit on IBM quantum computer
• Calculating response functions of coupled oscillators using quantum phase estimation
• Resource Reduction in Multiplexed High-Dimensional Quantum Reed-Solomon Codes
• Quantum entanglement percolation under a realistic restriction
• Implementation of analytic functions with quantum gates
• A prime factorization based on quantum dynamics on a spin ensemble (I)
• Flexible Representation and Manipulation of Audio Signals on Quantum Computers
• A quantum algorithm for greatest common divisor problem
• The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
• Circuit-based Modular Implementation of Quantum Ghost Imaging
• The Landauer Resistance and Band Spectra for the Counting Quantum Turing Machine
• Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
• Quantum Image Rotation by an arbitrary angle
• Quantum circuit to estimate pi using quantum amplitude estimation
• Graphical Calculi and their Conjecture Synthesis
• The Representation of Numbers in Quantum Mechanics
• A Synthesis of Hidden Subgroup Quantum Algorithms and Quantum Chemical Dynamics
• Tradeoff between noise and banding in a quantum adder with qudits
• Efficient Estimation and Sequential Optimization of Cost Functions in Variational Quantum Algorithms
• Exploration of Design Alternatives for Reducing Idle Time in Shor's Algorithm: A Study on Monolithic and Distributed Quantum Systems
• Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q
• Implementing Quantum Gates Using Length-3 Dynamic Quantum Walks
• Generalization of CNOT-based Discrete Circular Quantum Walk: Simulation and Effect of Gate Errors
• Quantum Algorithm Processor For Finding Exact Divisors
• Imitating quantum mechanics: qubit-based model for simulation
• Quantum Heaviside Eigen Solver
• Ancilla-Input and Garbage-Output Optimized Design of a Reversible Quantum Integer Multiplier
• Classical Control of Large-Scale Quantum Computers
• Reversible Logic Based Concurrent Error Detection Methodology For Emerging Nanocircuits
• An Algorithm to Speed Up Quantum Search
• Operator Imprecision and Scaling of Shor's Algorithm
• Quantum oracles for the finite element method
• DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing
• A Measurement-Based Form of the Out-of-Place Quantum Carry-Lookahead Adder
• A quantum algorithm for computing the Carmichael function
• A Universal Quantum Computing Virtual Machine
• Graph comparison via nonlinear quantum search
• A Multilayer Network Approach to Quantum Computing
• Quantum Harmonic Sieve: Learning DNF with a Classical Example Oracle
• Linear Order Matrix Inversion Method with Help from Quantum Searching Algorithm
• A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation
• From Fermat's last theorem to the quantum computer
• Implementing Bilinear Interpolation on Quantum Images
• Quantum simulation and circuit design for solving multidimensional Poisson equations
• Exploring the Impact of Affine Loop Transformations in Qubit Allocation
• Quantum Speedup of Monte Carlo Integration with respect to the Number of Dimensions and its Application to Finance
• Halving the width of Toffoli based constant modular addition to n+3 qubits