# Is there a general order finding quantum algorithm for a given a and N?

Quantum Computing Asked by happy_sisyphus on December 16, 2020

I’m trying to construct a general circuit for Shor’s algorithm in Qiskit. I understood the later parts of the circuit (inverse QFT and QPE), but can’t really understand the order finding.
For example, if we consider $$N=15$$, we have all the $$text{gcd}$$ of 15 to be 2,7,8,11,13 (although I suspect that 4 is not considered as it is $$2^2$$). For $$a=2 ,text{or}, 13$$, we swap qubits 0 and 1, 1 and 2, 2 and 3. If $$a=7 ,text{or}, 8$$, we swap 2 and 3, 1 an 2, 0 and 1. If $$a=11$$, we swap 1 and 3, 0 and 2. Also, if $$a=7, 11 ,text{or}, 13$$, we add an X gate on all the 4 added qubits.

I want to know how we chose which qubits to swap for a particular number, and how we can generalize it, if possible.

In general, you need to use modular exponentiation algorithm. In Qiskit tutorial, I guess they saw some pattern to for that specific case to implement operator $$U$$. Yet you can use the following idea to create operator $$U$$. Let's suppose that $$a=11$$ and $$N=21$$. u is the matrix that corresponds to operator $$U$$. By using u, you should be able to create a gate. Note that we are cheating since if you do all below operations, you already know the order $$r$$ and there is no need for order finding algorithm.

import numpy as np
u = np.zeros([32, 32], dtype = int)

for i in range(21):
u[11*i%21][i]=1
for i in range(21,32):
u[i][i]=1



Answered by usercs on December 16, 2020

I shall explain taking the case of a = 2. The process is the same for any other value of a you have mentioned.

So to factor N = 15, you need the gates $$U^4$$, $$U^2$$ and $$U^1$$ gates. Where U performs the following operation $$U|yrangle = |yamodNrangle$$
$$U^2|yrangle = |ya^2modNrangle$$
$$U^4|yrangle = |ya^4modNrangle$$

We first apply $$U^4$$ then $$U^2$$ and finally $$U^1$$. I am assuming that you are aware that we start Shor's algorithm by giving an input $$|1rangle$$ to $$U^4$$ which simply performs $$|16mod15rangle = |1rangle$$. Actually if you try out all the possible input values you will realise that $$U^4$$ is actually an identity operation.

For $$U^2$$, the operation performed is $$U^2|1rangle = |4mod15rangle = |4rangle$$. Now in shors algorithm the size of the register on which U acts is 4 qubits (for N = 15, as 4 qubit are needed to represent 15, size of register is $$log_2(n)$$). So $$|1rangle$$ is represented by 0001 and similarly $$|4rangle$$ by 0100. Therefore we need to swap 1st and third row. This is the general procedure.

Now the two possible kets which may enter $$U$$ are $$|1rangle$$ and $$|4rangle$$. So you need to be able to map them to $$|2rangle$$ and $$|8rangle$$ respectively. Which is a mapping from 0001 and 0100 to 0010 and 1000 respectively. Hence the first mapping demands swapping of bits 1 and 2 and the second mapping demands swapping qubits 3 and 4. This is the process of designing these gates. In your question you have talked about U gate. You can either create $$U^2$$ by applying U twice or by the method I have described above. Hope this helps!

Answered by siddg on December 16, 2020

## Related Questions

### How well defined is $log(P)$ for $P$ projection?

1  Asked on August 20, 2021 by r-w

### Where to publish quantum algorithm related paper

2  Asked on August 20, 2021 by zzy1130

### Can a Kraus representation act as the identity on any operator?

4  Asked on August 20, 2021

### Am I doing anything wrong when trying to calculate the expectation value in Qiskit on the real hardware?

1  Asked on August 20, 2021 by stinglikeabeer

### Representing a von Neumann measurement as $[mathcal{I} otimes P_i] U(rho_s otimes rho_a)U^{-1} [mathcal{I} otimes P_i]$, how do we choose $U$?

0  Asked on August 20, 2021

### Relation between Wigner quasi-probabability distribution and statistical second-moment

1  Asked on August 20, 2021 by kianoosh-kargar

### What does the adjoint of a channel represent physically?

3  Asked on August 20, 2021

### Is it possible to detect the phase $pi$ or 0 for the single qubit circuit X H P?

1  Asked on August 20, 2021 by psanfi

### Equivalence checking of quantum circuits up to error

0  Asked on August 20, 2021 by marsl

### Defining a Grassmann Algebra in Python

0  Asked on August 20, 2021 by callum

### What is the status of confirming the existence of anyons?

1  Asked on August 20, 2021 by user1271772

### Motivation for the definition of k-distillability

1  Asked on August 20, 2021

### Geometric interpretation of 1-distillability

0  Asked on August 20, 2021 by sanchayan-dutta

### What is the general matrix for the Swap gate?

1  Asked on August 20, 2021 by victory-omole

### What is the pseudo threshold of a QECC using stabilizer formalism

2  Asked on August 20, 2021 by el-mo

### Why attenuator and not filters for QC driving line

2  Asked on August 20, 2021

### How do you turn the CX gate upside down on ibm-q-experience?

2  Asked on August 20, 2021

### Is communication possible with entanglement?

3  Asked on August 20, 2021

### Is the quantum min-relative entropy $D_{min}(rho|sigma)=-log(F(rho, sigma)^2)$ or $D_{min}(rho|sigma)=-log(tr(Pi_rhosigma))$?

1  Asked on August 20, 2021