The first thing we will do is implement multiplication by 8 mod 35 on a quantum computer (that is, we will implement the f(x) = 8x (mod 35) function). The brute-force way to do this would be to take a classical program to compute the function:
def 8xmod35(x):
return 8*x % 35
Then, from the assembly language this Python corresponds to, we need to rewrite that assembly language in terms of just the AND and NOT gates. The final step would be to switch the bits to qubits, the AND gates to quantum AND gates, and the NOT gates to quantum NOT gates, adding in extra qubits where necessary as the reversibility of of the quantum AND gate and quantum NOT gates require ancillary qubits. In this brute-force translation approach from a classical computer to a quantum computer, we would end up with a gigantic number of qubits. This number of qubits would not be practical as the more qubits an algorithm uses, the more difficult it is to engineer a quantum algorithm that is reliable and can run on real-world hardware. Therefore, we cannot practically take the brute-force translation approach.
Instead, we can use some mathematical tricks to minimize the number of qubits required for the computation. The key thing to realize is that since we are always taking 8x (mod 35), the f(x) result will always be between 0 and 34. The second thing to realize is that there is the potential for cycles in the results. The following is one example:
8*1 mod 35 = 8
8*8 mod 35 = 29
8*29 mod 35 = 22
8*22 mod 35 = 1
Here is another example:
8*2 mod 35 = 16
8*16 mod 35 = 23
8*23 mod 35 = 9
8*9 mod 35 = 2
Finding the modular multiplication map for 8x (mod 35) is a bit more involved. Here is a bit of code that can compute the modular multiplication map for any value of a (here a = 8) and any value of N (here, N = 35):
def U_a_modN(a,N,binary=False):
"""
a and N are decimal
This algorithm returns U_a where:
U_a is a modular multiplication operator map from |x> to |ax mod N>
If binary is set to True, the mapping is given in binary instead of in decimal notation.
"""
res={}
l=[]
for i in range(1,N):
l+=[a*i%N]
res=set()
for i in range(1,N):
mp=[i]
end=i
nxt=i-1
while l[nxt]!=end:
mp+=[l[nxt]]
nxt=l[nxt]-1
res.add(tuple(mp))
final_res=[]
for item in res:
dup=False
for final_item in final_res:
if set(item) == set(final_item):
dup=True
if not dup:
final_res+=[item]
if not binary:
return final_res
else:
final_res_bin=[]
for mapping in final_res:
final_res_bin+=[tuple(['{0:06b}'.format(decimal)
for decimal in mapping])]
return final_res_bin
The results for a = 8 and N = 35 in decimal and binary are then computed with the following commands:
print(U_a_modN(8,35))
print(U_a_modN(8,35,binary=True))
This prints the following:
[(7, 21, 28, 14), (34, 27, 6, 13), (2, 16, 23, 9), (26, 33, 19, 12), (18, 4, 32, 11), (24, 17, 31, 3), (15,), (30,), (5,), (8, 29, 22, 1), (20,), (10,), (25,)]
[('000111', '010101', '011100', '001110'), ('100010', '011011', '000110', '001101'), ('000010', '010000', '010111', '001001'), ('011010', '100001', '010011', '001100'), ('010010', '000100', '100000', '001011'), ('011000', '010001', '011111', '000011'), ('001111',), ('011110',), ('000101',), ('001000', '011101', '010110', '000001'), ('010100',), ('001010',), ('011001',)]
For 8x (mod 35), all the possible cycles in the values of x are as follows (since each of the tuples are a cycle, we can choose any entry point to the cycle; here, I adopt the convention of having the entry points to the cycle be the lowest value in the tuple, and then ordering the cycles by that first entry point):
1 | 8 | 29 | 22 | 1
2 | 16 | 23 | 9 | 2
3 | 24 | 17 | 31 | 3
4 | 32 | 11 | 18 | 4
5 | 5
6 | 13 | 34 | 27 | 6
10 | 10
12 | 26 | 33 | 19 | 12
15 | 15
20 | 20
25 | 25
30 | 30
What does this mean? Well, it means that if we know what x is (say, 3), we can easily compute the result for x = 24, x = 17, and x = 31 using the preceding map. Since 35 in binary is 100011, it is six bits long, and that means that each input to f(x) (say, x = 8 or in binary: 001000) will simply map the binary representation of the input to an output according to preceding the map. In this case, f(8) is equivalent to f(001000) in binary and the result should be 29 in decimal or 011101 in binary.
Our quantum circuit to implement this has to do the same. If the input is |001000>, it should output |011101>, and so on for each of the series of numbers. So, to create the correct circuit for f(x) = 8x (mod 35), we need to do the following:
- Find the groups of repetitions
- Convert decimal to binary
- Create an algorithm that changes one binary to the next consistently
Can you spot the pattern to help create the circuit in the binary? I can't. This example is much more involved than factoring N = 15. These patterns are not apparent in terms of moving from one item in the modular multiplication map to the next. In fact, rather than trying to reinvent the wheel and spot the patterns, we can consult the paper Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation (Markov and Saeedi 2015) https://arxiv.org/pdf/1202.6614.pdf. This details how to make an algorithm that creates modular multiplication circuits of a small size compared to the brute-force technique of just taking the classical computation and translating quantum gates into classical gates. For those who like a challenge, doing this for 8x (mod 35) is a chapter exercise.