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.

2 Answers

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):
for i in range(21,32):

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

Add your own answers!

Related Questions

Where to publish quantum algorithm related paper

2  Asked on August 20, 2021 by zzy1130


Defining a Grassmann Algebra in Python

0  Asked on August 20, 2021 by callum


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


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP