Exponentiation performed over a modulus. The operation of modular exponentiation calculates the remainder when an integer b (the base) raised to the eth power (the exponent), b^e, is divided by a positive integer m (the modulus).
Questions tagged [modular-exponentiation]
19 questions
7
votes
1 answer
Specialized/hardcoded modular exponentiation circuit for Shor's
While researching to implement Shor's algorithm, I came across the following curcuit diagram (diagram 1).
And while researching for how to implement the U operator, I came across the following circuit diagram (diagram 2).
The circuit in diagram 2…
shrini1000
- 285
- 8
5
votes
1 answer
Cost of Modular Exponentiation in Shor's algorithm
In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as
$$
U|y\rangle=|xy\;(\mod N)\rangle\text{ for } 0\leq y\leq N-1\\
U|y\rangle=|y\rangle\text{…
SOORAJ SOMAN
- 891
- 4
- 16
3
votes
1 answer
Implementation of Modular Exponentiation Function in Shor's Algorithm
In this paper on the modular exponentiation function of Shor's Algorithm the author mentions creating a special circuit that decomposes the function $f(x)=a^x \mod N$ into
$$(...((a^{x_02^0} \mod N) \times a^{x_12^1} \mod N) \times ...) \times…
Mark A
- 142
- 7
3
votes
2 answers
How to implement the modular exponentiation implementation in Shor's algorithm?
I am trying to implement Shor's algorithm using modular exponentiation as described in this paper: https://arxiv.org/abs/quant-ph/0205095
The issue is found when trying to implement CMULT($a^{-1}$)mod(N)
Since we can only use integers, do you know…
Juan Manuel Pavon
- 31
- 3
3
votes
2 answers
Why is this modular adder so complicated?
I'm trying to construct a controlled modular multiplication circuit and a subcomponent is a modular adder. However, it appears the basic Draper/Fourier adder is already modular. Shouldn't adding $N=2^n$ to $a$ cause the phase to multiplied by…
Jackson Walters
- 351
- 1
- 9
3
votes
0 answers
How to create this feature map?
In this paper, the following feature map is used:
$$x \to \vert\phi(x)\rangle = \frac{1}{\sqrt{2^k}}\sum_{i=0}^{2^k-1}\vert x\cdot g^i\rangle$$
But no circuit is provided. A theoretical description of the circuit is provided in the supplementary…
akkh
- 51
- 4
3
votes
1 answer
Quantum Phase Estimation Circuit and Modular Exponentiaton
In Nielsen and Chuang, it is stated that the effect of phase estimation circuit is mapping state $|j\rangle |u\rangle$ to $|j\rangle U^j |u\rangle$.
Here is my solution:
Consider the first $CU^{2^0}$. Let $|j\rangle = |j_1j_2\dots j_t\rangle$. It…
usercs
- 481
- 2
- 9
2
votes
1 answer
Efficient creation of a modular multiplicative inverse gate using Fermat's Little Theorem
I'm wondering if anyone has ever stumbled upon an efficient way to create a gate that can calculate the multiplicative modular inverse in $\mathbb{Z}_p$, it may even be that somebody has stumbled upon it by accident, without being aware of Fermat's…
Ramezzez
- 166
- 6
2
votes
3 answers
Shor: Modular exponentiation vs modular multiplication
In his original article Polynomial-Time Algorithms for Prime Factorization
and Discrete Logarithms on a Quantum Computer, Peter Shor constructed an algorithm for finding a period $r$ of the modular exponentiation $a^x \mod N$, where $N$ is factored…
Martin Vesely
- 15,244
- 4
- 32
- 75
2
votes
0 answers
How to do modular exponentiation in qiskit with gates?
I understand the following code on why the specific swaps take place, but when I try to replicate it with $N=35$, I get confused.
def c_amod15(a, x):
if a not in [2,4,7,8,11,13]:
raise ValueError("'a' must be 2,7,8,11,13")
U = QuantumCircuit(4) …
James Garcia
- 21
- 1
2
votes
0 answers
Shor's algorithm in Python with qiskit - How to implement the modular exponentiation step?
I found this code for Shor's algorithm but it always was failing at the end of the modular_exponentiation routine because the keyvalue of '00000' was not found in the dictionary on the call to b_measure = result.get_counts()[format(i,…
user67105
- 21
- 1
2
votes
1 answer
When factoring N=21 on IBMQ Devices with Shor's algorithm, does the quantum subroutine require modular exponentiation?
I am currently working on Qiskit code implementing Shor algorithm in the form of a quantum circuit. I am factoring $N = 21$ (into 3 and 7) using 5 qubits, with 3 qubits in the work register and 2 in the control. The purpose is that a random integer…
Sam_QC
- 109
- 10
1
vote
2 answers
A concrete 4-qubit circuit that computes $ a^j \mod{15}$?
As a follow up to a previous question on period finding and factoring, could anyone give a real construction of a 4-qubit circuit that can output (in the same 4-qubit binary format)
$$ a^j \mod{15}$$
for any free choice of $a$ and $j =…
James
- 551
- 3
- 11
1
vote
1 answer
7*4 mod(15) qiskit explanation
I don't understand this circuit's output from Qiskit's doc : .
Indeed, the result should be 13, but output, I think I don't have the right method to read the result. I should have $|1101\rangle$ but we can see $|1110\rangle$ instead. Maybe the right…
Jonah
- 23
- 3
1
vote
1 answer
Shor's Algorithm and Permutations
I read some articles about Shor's algorithm but I can't understand how it works. From my point of view it makes the problem even more complex from O(2^n) to O(n!). How does the oracle that is suppose to solve the modular division simultaneously…
Martin Spinoza
- 31
- 2