Take and . The orbit of modulo is , so the order is . The bit length of is , and…

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm

Problem

Take

N = 5

and

a = 2

. The orbit of

2

modulo

5

2, 4, 3, 1

, so the order is

r = 4

. The bit length of

N

L = \lceil \log_2 5 \rceil = 3

, and order finding is run with the register size

t = 2L+1 = 7

control qubits (no extra qubits for the error tolerance). ((a)) State the size of the measured output register,

2^t

. ((b)) Since

r

divides

2^t

exactly, list every possible measured value of the output register and its probability.

Browse the problem library