· 7 years ago · Nov 18, 2018, 04:14 PM
1"""Primitive circuit operations on quantum circuits."""
2
3from sympy import Symbol, Integer, Tuple, Mul, sympify
4from sympy.utilities import numbered_symbols
5from sympy.physics.quantum.gate import Gate
6
7__all__ = [
8 'kmp_table',
9 'find_subcircuit',
10 'replace_subcircuit',
11 'convert_to_symbolic_indices',
12 'convert_to_real_indices',
13 'random_reduce',
14 'random_insert'
15]
16
17def kmp_table(word):
18 """Build the 'partial match' table of the
19 Knuth-Morris-Pratt algorithm.
20
21 Note: This is applicable to strings or
22 quantum circuits represented as tuples.
23 """
24
25 # Current position in subcircuit
26 pos = 2
27 # Beginning position of candidate substring that
28 # may reappear later in word
29 cnd = 0
30 # The 'partial match' table that helps one determine
31 # the next location to start substring search
32 table = list()
33 table.append(-1)
34 table.append(0)
35
36 while pos < len(word):
37 if word[pos-1] == word[cnd]:
38 cnd = cnd + 1
39 table.append(cnd)
40 pos = pos + 1
41 elif cnd > 0:
42 cnd = table[cnd]
43 else:
44 table.append(0)
45 pos = pos + 1
46
47 return table
48
49def find_subcircuit(circuit, subcircuit, start=0, end=0):
50 """Finds the subcircuit in circuit, if it exists.
51
52 If the subcircuit exists, the index of the start of
53 the subcircuit in circuit is returned; otherwise,
54 -1 is returned. The algorithm that is implemented
55 is the Knuth-Morris-Pratt algorithm.
56
57 Parameters
58 ==========
59 circuit : tuple, Gate or Mul
60 A tuple of Gates or Mul representing a quantum circuit
61 subcircuit : tuple, Gate or Mul
62 A tuple of Gates or Mul to find in circuit
63 start : int
64 The location to start looking for subcircuit.
65 If start is the same or past end, -1 is returned.
66 end : int
67 The last place to look for a subcircuit. If end
68 is less than 1 (one), then the length of circuit
69 is taken to be end.
70
71 Examples
72 ========
73
74 Find the first instance of a subcircuit:
75
76 >>> from sympy.physics.quantum.circuitutils import find_subcircuit
77 >>> from sympy.physics.quantum.gate import X, Y, Z, H
78 >>> circuit = X(0)*Z(0)*Y(0)*H(0)
79 >>> subcircuit = Z(0)*Y(0)
80 >>> find_subcircuit(circuit, subcircuit)
81 1
82
83 Find the first instance starting at a specific position:
84
85 >>> find_subcircuit(circuit, subcircuit, start=1)
86 1
87
88 >>> find_subcircuit(circuit, subcircuit, start=2)
89 -1
90
91 >>> circuit = circuit*subcircuit
92 >>> find_subcircuit(circuit, subcircuit, start=2)
93 4
94
95 Find the subcircuit within some interval:
96
97 >>> find_subcircuit(circuit, subcircuit, start=2, end=2)
98 -1
99 """
100
101 if isinstance(circuit, Mul):
102 circuit = circuit.args
103
104 if isinstance(subcircuit, Mul):
105 subcircuit = subcircuit.args
106
107 if len(subcircuit) == 0 or len(subcircuit) > len(circuit):
108 return -1
109
110 if end < 1:
111 end = len(circuit)
112
113 # Location in circuit
114 pos = start
115 # Location in the subcircuit
116 index = 0
117 # 'Partial match' table
118 table = kmp_table(subcircuit)
119
120 while (pos + index) < end:
121 if subcircuit[index] == circuit[pos + index]:
122 index = index + 1
123 else:
124 pos = pos + index - table[index]
125 index = table[index] if table[index] > -1 else 0
126
127 if index == len(subcircuit):
128 return pos
129
130 return -1
131
132def replace_subcircuit(circuit, subcircuit, replace=None, pos=0):
133 """Replaces a subcircuit with another subcircuit in circuit,
134 if it exists.
135
136 If multiple instances of subcircuit exists, the
137 first instance is replaced. A location to check may
138 be optionally given. If subcircuit can't be found,
139 circuit is returned.
140
141 Parameters
142 ==========
143 circuit : tuple, Gate or Mul
144 A quantum circuit
145 subcircuit : tuple, Gate or Mul
146 The circuit to be replaced
147 replace : tuple, Gate or Mul
148 The replacement circuit
149 pos : int
150 The location to start search and replace
151 subcircuit, if it exists. This may be used
152 if it is known beforehand that multiple
153 instances exist, and it is desirable to
154 replace a specific instance. If a negative number
155 is given, pos will be defaulted to 0.
156
157 Examples
158 ========
159
160 Find and remove the subcircuit:
161
162 >>> from sympy.physics.quantum.circuitutils import replace_subcircuit
163 >>> from sympy.physics.quantum.gate import X, Y, Z, H
164 >>> circuit = X(0)*Z(0)*Y(0)*H(0)*X(0)*H(0)*Y(0)
165 >>> subcircuit = Z(0)*Y(0)
166 >>> replace_subcircuit(circuit, subcircuit)
167 (X(0), H(0), X(0), H(0), Y(0))
168
169 Remove the subcircuit given a starting search point:
170
171 >>> replace_subcircuit(circuit, subcircuit, pos=1)
172 (X(0), H(0), X(0), H(0), Y(0))
173
174 >>> replace_subcircuit(circuit, subcircuit, pos=2)
175 (X(0), Z(0), Y(0), H(0), X(0), H(0), Y(0))
176
177 Replace the subcircuit:
178
179 >>> replacement = H(0)*Z(0)
180 >>> replace_subcircuit(circuit, subcircuit, replace=replacement)
181 (X(0), H(0), Z(0), H(0), X(0), H(0), Y(0))
182 """
183
184 if pos < 0:
185 pos = 0
186
187 if isinstance(circuit, Mul):
188 circuit = circuit.args
189
190 if isinstance(subcircuit, Mul):
191 subcircuit = subcircuit.args
192
193 if isinstance(replace, Mul):
194 replace = replace.args
195 elif replace is None:
196 replace = ()
197
198 # Look for the subcircuit starting at pos
199 loc = find_subcircuit(circuit, subcircuit, start=pos)
200
201 # If subcircuit was found
202 if loc > -1:
203 # Get the gates to the left of subcircuit
204 left = circuit[0:loc]
205 # Get the gates to the right of subcircuit
206 right = circuit[loc + len(subcircuit):len(circuit)]
207 # Recombine the left and right side gates into a circuit
208 circuit = left + replace + right
209
210 return circuit
211
212def _sympify_qubit_map(mapping):
213 new_map = {}
214 for key in mapping:
215 new_map[key] = sympify(mapping[key])
216 return new_map
217
218def convert_to_symbolic_indices(seq, start=None, gen=None, qubit_map=None):
219 """Returns the circuit with symbolic indices and the
220 dictionary mapping symbolic indices to real indices.
221
222 The mapping is 1 to 1 and onto (bijective).
223
224 Parameters
225 ==========
226 seq : tuple, Gate/Integer/tuple or Mul
227 A tuple of Gate, Integer, or tuple objects, or a Mul
228 start : Symbol
229 An optional starting symbolic index
230 gen : object
231 An optional numbered symbol generator
232 qubit_map : dict
233 An existing mapping of symbolic indices to real indices
234
235 All symbolic indices have the format 'i#', where # is
236 some number >= 0.
237 """
238
239 if isinstance(seq, Mul):
240 seq = seq.args
241
242 # A numbered symbol generator
243 index_gen = numbered_symbols(prefix='i', start=-1)
244 cur_ndx = index_gen.next()
245
246 # keys are symbolic indices; values are real indices
247 ndx_map = {}
248
249 def create_inverse_map(symb_to_real_map):
250 rev_items = lambda item: tuple([item[1], item[0]])
251 return dict(map(rev_items, symb_to_real_map.items()))
252
253 if start is not None:
254 if not isinstance(start, Symbol):
255 msg = 'Expected Symbol for starting index, got %r.' % start
256 raise TypeError(msg)
257 cur_ndx = start
258
259 if gen is not None:
260 if not isinstance(gen, numbered_symbols().__class__):
261 msg = 'Expected a generator, got %r.' % gen
262 raise TypeError(msg)
263 index_gen = gen
264
265 if qubit_map is not None:
266 if not isinstance(qubit_map, dict):
267 msg = ('Expected dict for existing map, got ' +
268 '%r.' % qubit_map)
269 raise TypeError(msg)
270 ndx_map = qubit_map
271
272 ndx_map = _sympify_qubit_map(ndx_map)
273 # keys are real indices; keys are symbolic indices
274 inv_map = create_inverse_map(ndx_map)
275
276 sym_seq = ()
277 for item in seq:
278 # Nested items, so recurse
279 if isinstance(item, Gate):
280 result = convert_to_symbolic_indices(item.args,
281 qubit_map=ndx_map,
282 start=cur_ndx,
283 gen=index_gen)
284 sym_item, new_map, cur_ndx, index_gen = result
285 ndx_map.update(new_map)
286 inv_map = create_inverse_map(ndx_map)
287
288 elif isinstance(item, tuple) or isinstance(item, Tuple):
289 result = convert_to_symbolic_indices(item,
290 qubit_map=ndx_map,
291 start=cur_ndx,
292 gen=index_gen)
293 sym_item, new_map, cur_ndx, index_gen = result
294 ndx_map.update(new_map)
295 inv_map = create_inverse_map(ndx_map)
296
297 elif item in inv_map:
298 sym_item = inv_map[item]
299
300 else:
301 cur_ndx = gen.next()
302 ndx_map[cur_ndx] = item
303 inv_map[item] = cur_ndx
304 sym_item = cur_ndx
305
306 if isinstance(item, Gate):
307 sym_item = item.__class__(*sym_item)
308
309 sym_seq = sym_seq + (sym_item,)
310
311 return sym_seq, ndx_map, cur_ndx, index_gen
312
313def convert_to_real_indices(seq, qubit_map):
314 """Returns the circuit with real indices.
315
316 Parameters
317 ==========
318 seq : tuple, Gate/Integer/tuple or Mul
319 A tuple of Gate, Integer, or tuple objects or a Mul
320 qubit_map : dict
321 A dictionary mapping symbolic indices to real indices.
322
323 Examples
324 ========
325
326 Change the symbolic indices to real integers:
327
328 >>> from sympy import Symbol
329 >>> from sympy.physics.quantum.circuitutils import \
330 convert_to_real_indices
331 >>> from sympy.physics.quantum.gate import X, Y, Z, H
332 >>> i0 = Symbol('i0'); i1 = Symbol('i1')
333 >>> index_map = {i0 : 0, i1 : 1}
334 >>> convert_to_real_indices(X(i0)*Y(i1)*H(i0)*X(i1), index_map)
335 (X(0), Y(1), H(0), X(1))
336 """
337
338 if isinstance(seq, Mul):
339 seq = seq.args
340
341 if not isinstance(qubit_map, dict):
342 msg = 'Expected dict for qubit_map, got %r.' % qubit_map
343 raise TypeError(msg)
344
345 qubit_map = _sympify_qubit_map(qubit_map)
346 real_seq = ()
347 for item in seq:
348 # Nested items, so recurse
349 if isinstance(item, Gate):
350 real_item = convert_to_real_indices(
351 item.args, qubit_map)
352
353 elif isinstance(item, tuple) or isinstance(item, Tuple):
354 real_item = convert_to_real_indices(
355 item, qubit_map)
356
357 else:
358 real_item = qubit_map[item]
359
360 if isinstance(item, Gate):
361 real_item = item.__class__(*real_item)
362
363 real_seq = real_seq + (real_item,)
364
365 return real_seq
366
367def random_reduce(circuit, gate_ids, seed=None):
368 """Shorten the length of a quantum circuit.
369
370 random_reduce looks for circuit identities in circuit, randomly chooses
371 one to remove, and returns a shorter yet equivalent circuit. If no
372 identities are found, the same circuit is returned.
373
374 Parameters
375 ==========
376 circuit : Gate tuple of Mul
377 A tuple of Gates representing a quantum circuit
378 gate_ids : list, GateIdentity
379 List of gate identities to find in circuit
380 seed : int or list
381 seed used for _randrange
382 """
383 from sympy.utilities.randtest import _randrange
384
385 if len(gate_ids) < 1:
386 return circuit
387
388 if isinstance(circuit, Mul):
389 circuit = circuit.args
390
391 # Create the random integer generator with the seed
392 randrange = _randrange(seed)
393
394 # Flatten the GateIdentity objects (with gate rules)
395 # into one single list
396 collapse_func = lambda acc, an_id: acc + list(an_id.equivalent_ids)
397 ids = reduce(collapse_func, gate_ids, [])
398 found = False
399
400 # Look for an identity in circuit
401 while len(ids) > 0 and not found:
402 remove_index = randrange(0, len(ids))
403 remove_id = ids[remove_index]
404 ids.remove(remove_id)
405 found = find_subcircuit(circuit, remove_id) > -1
406
407 # Remove the identity
408 if found:
409 circuit = replace_subcircuit(circuit, remove_id)
410
411 return circuit
412
413def random_insert(circuit, choices, seed=None, insert_loc=None, insert_circuit_loc=None):
414 """Insert a circuit into another quantum circuit.
415
416 random_insert randomly selects a circuit from choices and randomly chooses
417 a location to insert into circuit.
418
419 Parameters
420 ==========
421 circuit : Gate tuple or Mul
422 A tuple or Mul of Gates representing a quantum circuit
423 choices : list
424 Set of circuit choices
425 seed : int or list
426 seed used for _randrange
427 insert_loc : int
428 Value used for the insert location. If none is given, one is chosen
429 at random.
430 insert_circuit_loc : int
431 Value used for the circuit choice. If none is given, one is chosen
432 at random.
433
434 """
435 from sympy.utilities.randtest import _randrange
436
437 if len(choices) < 1:
438 return circuit
439
440 if isinstance(circuit, Mul):
441 circuit = circuit.args
442
443 # get the insertion locations (randomly, if not provided)
444 seed = [insert_loc] if insert_loc is not None else seed
445 insert_loc = _randrange(seed)(len(circuit))
446 seed = [insert_circuit_loc] if insert_loc is not None else seed
447 insert_circuit_loc = _randrange(seed)(len(choices))
448
449 insert_circuit = choices[insert_circuit_loc]
450
451 left = circuit[0: insert_loc]
452 right = circuit[insert_loc: len(circuit)]
453
454 return left + insert_circuit + right