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

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP