Mercurial > repo

comparison interps/qbf/qubit.py @ 996:859f9b4339e6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
<Gregor> tar xf egobot.tar.xz
author HackBot
date Sun, 09 Dec 2012 19:30:08 +0000
parents
children
comparison
equal deleted inserted replaced
995:6883f5911eb7 996:859f9b4339e6
1 # A qubit library
2 # Author: Nikita Ayzikovsky (lament)
3 # You may use this freely, but it's neither GPL nor public domain (yet)
4
5 # Note that everything starts out initialized to 1. This needs to be
6 # changed if this is to be used for something other than Quantum Brainfuck.
7 # Other than that, the library is completely generic. Just add your own
8 # gates and go ahead.
9
10 # The things that should be actually used from outside are
11 # clases Gate and Register.
12
13 import random # of course!
14
15 def dotproduct(a,b):
16 """Because I'm too lazy to look for a lin. algebra module"""
17 return sum([x*y for (x,y) in zip(a,b)])
18
19 def mvmult(matrix, vector):
20 """Because I'm too lazy to look for a lin. algebra module"""
21 #no error checking for now
22 result = []
23 for row in matrix:
24 result.append(dotproduct(row, vector))
25 return result
26
27 def bit(num, bitnum):
28 return int((num&(1<<bitnum)) != 0)
29
30 def n2bits(n, length):
31 return [bit(n, x) for x in range(length)]
32
33 def bits2n(bitlist):
34 result = 0
35 for x in range(len(bitlist)):
36 result += bitlist[x] * (1<<x)
37 return result
38
39 class Gate:
40 def __init__(self, num_bits, matrix):
41 self.num_bits = num_bits
42 self.N = 1<<num_bits
43 self.matrix = matrix
44 def apply(self, register, bitlist):
45 """Applies this gate to bits from bitlist (size of bitlist should
46 be N) in the register object given"""
47 # let's do this the least efficient way possible
48 # apply the gate to bits in bitlist for each individual combination
49 # of other bits
50 # We have register.length total bits, so register.length-N
51 # bit combinations
52
53 new_contents = register.contents[:]
54
55 num_bits = register.length
56 allbits = range(num_bits)
57 otherbits = [x for x in allbits if x not in bitlist]
58 # Iterate over each combination of other bits:
59 for i in range(2**len(otherbits)):
60 other_bit_values = n2bits(i, len(otherbits))
61 positions = []
62 for j in range(self.N):
63 current_position = [0] * num_bits
64 for index, value in zip(otherbits, other_bit_values):
65 current_position[index] = value
66 for index, value in zip(bitlist,n2bits(j, self.N)):
67 current_position[index] = value
68 positions.append(bits2n(current_position))
69 values = [register.contents[x] for x in positions]
70 values = mvmult(self.matrix, values)
71 for x, index in zip(positions, range(self.N)):
72 new_contents[x] = values[index]
73 register.contents = new_contents
74
75 class Register:
76 def __init__(self, length):
77 """Initialize to all 1s as per Quantum Brainfuck specs"""
78 self.length = length
79 self.contents = [0] * (2**length)
80 self.contents[-1] = 1
81 def add_bit(self):
82 """Adds a new qubit, containing 1 and not entangled with anything"""
83 new_contents = []
84 new_contents = [0] * len(self.contents) + self.contents
85 self.contents = new_contents
86 self.length += 1
87 def observe(self, bit_index):
88 """Observes the value of the qubit at the given index,
89 changing that bit to |0> or |1> and updating all probabilities
90 accordingly. Returns 0 or 1"""
91
92 # first, find out the probability that the qubit is set.
93 prob = 0
94 for i in range(2 ** self.length):
95 prob += abs(bit(i, bit_index) * self.contents[i]) ** 2
96 # prob is now set to the probability of bit set to 1
97 # now "Observe"
98 if random.random() <= prob:
99 bit_value = 1
100 else:
101 bit_value = 0
102 # now that we know the "observed" value, adjust all other
103 # probabilities to account for it.
104 if prob == 0 or prob == 1:
105 # don't need adjustment
106 return bit_value
107
108 adjustment = (1 / prob) ** 0.5
109 for i in range(2 ** self.length):
110 if bit(i, bit_index) == bit_value:
111 self.contents[i] = self.contents[i] * adjustment
112 else:
113 self.contents[i] = 0
114 return bit_value
115
116 def set(self, bit_index, bit_value):
117 """Sets the indexed bit to 'value', which should be 1 or 0"""
118 for i in range(2 ** self.length):
119 if bit(i, bit_index) == bit_value:
120 # take the 'sister' bit combination and add its
121 # probability to this one
122 if bit_value:
123 sister = i & (~ 1<<bit_index)
124 else:
125 sister = i | bit_index
126 total_prob = self.contents[i] **2 + self.contents[sister]**2
127 self.contents[i] = math.sqrt(total_prob)
128 self.contents[sister] = 0
129
130
131 #############################################################
132
133 import math
134 st = 1/math.sqrt(2)
135
136 Hadamard = Gate(1, [[st, st],
137 [st, -st]])
138
139 CNOT = Gate(2, [[1, 0, 0, 0],
140 [0, 1, 0, 0],
141 [0, 0, 0, 1],
142 [0, 0, 1, 0]])
143
144 CV = Gate(2, [[1, 0, 0, 0],
145 [0, 1, 0, 0],
146 [0, 0, 1, 0],
147 [0, 0, 0, 1j]])
148
149 if __name__ == '__main__':
150 # just testing stuff
151 r = Register(2)
152 Hadamard.apply(r, [0])
153 print r.contents
154 CNOT.apply(r,[1,0])
155 print r.contents
156 r.set(0, 1)
157 print r.contents