1# This file is part of QuTiP: Quantum Toolbox in Python. 2# 3# Copyright (c) 2011 and later, Paul D. Nation and Robert J. Johansson. 4# All rights reserved. 5# 6# Redistribution and use in source and binary forms, with or without 7# modification, are permitted provided that the following conditions are 8# met: 9# 10# 1. Redistributions of source code must retain the above copyright notice, 11# this list of conditions and the following disclaimer. 12# 13# 2. Redistributions in binary form must reproduce the above copyright 14# notice, this list of conditions and the following disclaimer in the 15# documentation and/or other materials provided with the distribution. 16# 17# 3. Neither the name of the QuTiP: Quantum Toolbox in Python nor the names 18# of its contributors may be used to endorse or promote products derived 19# from this software without specific prior written permission. 20# 21# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 24# PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25# HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32############################################################################### 33from collections import deque 34from copy import deepcopy 35from functools import cmp_to_key 36from random import shuffle 37 38from ..circuit import QubitCircuit, Gate 39from .instruction import Instruction 40 41 42class InstructionsGraph(): 43 """ 44 A directed acyclic graph (DAG) representation 45 of the quantum instruction dependency. 46 An example is Fig3(b) in https://doi.org/10.1117/12.666419. 47 It contains methods of generating the instruction dependency graph, 48 a list-schedule algorithm to find the topological order 49 and the computation of the distance in the weighted graph 50 (circuit latency). 51 52 It uses the `Instruction` object as a representation of node 53 and adds the following attributes to it: 54 55 predecessors, successors: dependency arrow of the DAG 56 distance_to_start, distance_to_end: longest distance to the start and end 57 58 Parameters 59 ---------- 60 instructions: list 61 A list of instructions 62 63 Attributes 64 ---------- 65 nodes: list 66 The input list of instruction with additional graph information. 67 start, end: list 68 List of indices of nodes connected to the start or end nodes. 69 """ 70 def __init__(self, instructions): 71 instructions = deepcopy(instructions) 72 self.nodes = [] 73 for instruction in instructions: 74 if isinstance(instruction, Gate): 75 self.nodes.append(Instruction(instruction)) 76 else: 77 self.nodes.append(instruction) 78 for node in self.nodes: 79 if node.duration is None: 80 node.duration = 1 81 self.start = None 82 self.end = None 83 84 def generate_dependency_graph(self, commuting): 85 """ 86 Generate the instruction dependency graph. 87 It modifies the class attribute `nodes`, where each element (node) 88 is an `Instruction`. 89 The graph is represented by attributes `predecessors` and 90 `successors`, each a set of indices 91 pointing to the position of the target node in the nodes list. 92 93 The graph preserves the mobility of the gates, 94 i.e. if two gates commute with each other, 95 such as ``CNOT 2, 3`` and ``CNOT 2, 1``, 96 there should be no dependency arrow between them. 97 Because of this, the generated graph does not consider 98 the hardware constraints, 99 e.g. two commuting gates addressing the same qubits 100 cannot be executed at the same time. 101 A dependency arrow between Instruction 1 and instruction 2 102 means that they do not commute. 103 However, the converse does not hold because we do not need 104 gate1->gate3 if we already have gate1->gate2->gate3. 105 106 Parameters 107 ---------- 108 commuting: function 109 A Python function that determines if two gates commute, 110 given that their used qubits overlap. 111 """ 112 # initialize the graph 113 for node in self.nodes: 114 node.predecessors = set() 115 node.successors = set() 116 117 num_qubits = max(set().union( 118 *[instruction.used_qubits for instruction in self.nodes])) + 1 119 qubits_instructions_dependency = [[set()] for i in range(num_qubits)] 120 # qubits_instructions_dependency: 121 # instruction dependency for each qubits, a nested list of level 3. 122 # E.g. [ 123 # [{1, }], 124 # [{0, 1}, {2, }], 125 # [{0, }] 126 # ] 127 # means that 128 # Gate0 acts on qubit 1 and 2, gate1 act on qubit0 and qubit1, 129 # but gate0 and gate1 cummute with each other. 130 # Therefore, there is not dependency between gate0 and gate1; 131 # Gate 2 acts on qubit1 and must be executed after gate0 and gate1. 132 # Hence, gate2 will depends on gate0 and gate1. 133 134 # Generate instruction dependency for each qubit 135 for current_ind, instruction in enumerate(self.nodes): 136 for qubit in instruction.used_qubits: 137 # For each used qubit, find the last dependency gate set. 138 # If the current gate commute with all of them, 139 # add it to the list. 140 # Otherwise, 141 # append a new set with the current gate to the list. 142 dependent = False 143 for dependent_ind in qubits_instructions_dependency[qubit][-1]: 144 if not commuting(current_ind, dependent_ind, self.nodes): 145 dependent = True 146 if not dependent: 147 qubits_instructions_dependency[qubit][-1].add(current_ind) 148 else: 149 qubits_instructions_dependency[qubit].append({current_ind}) 150 151 # Generate the dependency graph 152 for instructions_cycles in qubits_instructions_dependency: 153 for cycle_ind1 in range(len(instructions_cycles) - 1): 154 for instruction_ind1 in instructions_cycles[cycle_ind1]: 155 for instruction_ind2 in instructions_cycles[cycle_ind1+1]: 156 self.nodes[instruction_ind1].successors.add( 157 instruction_ind2) 158 self.nodes[instruction_ind2].predecessors.add( 159 instruction_ind1) 160 161 # Find start and end nodes of the graph 162 start = [] 163 end = [] 164 for i, instruction in enumerate(self.nodes): 165 if not instruction.successors: 166 end.append(i) 167 if not instruction.predecessors: 168 start.append(i) 169 self.start = start 170 self.end = end 171 172 def reverse_graph(self): 173 """ 174 Reverse the graph. 175 The start node becomes the end node 176 Predecessors and successors of each node are exchanged. 177 """ 178 for node in self.nodes: 179 node.predecessors, node.successors \ 180 = node.successors, node.predecessors 181 try: 182 self.distance_to_start, self.distance_to_end = \ 183 self.distance_to_end, self.distance_to_start 184 except AttributeError: 185 pass 186 self.start, self.end = self.end, self.start 187 188 def find_topological_order( 189 self, priority=True, apply_constraint=None, random=False): 190 """ 191 A list-schedule algorithm, it 192 finds the topological order of the directed graph 193 under certain constraint and priority indicator. 194 The function returns a list of cycles, 195 where each cycle is a list of instructions 196 that can be executed in parallel. 197 In the case of gates schedule, 198 the result will be the gates cycle list. 199 200 Parameters 201 ---------- 202 priority: bool 203 If use distance to the start and end nodes 204 as a priority measure for the schedule problem. 205 apply_constraint: function 206 A Python function that determines 207 if to instruction can be executed in parallel. 208 E.g. if two gates apply to the same qubit, the function 209 returns False. 210 211 Returns 212 ------- 213 cycles_list: list 214 A list of cycles, where each cycle is a list of instructions 215 that can be executed in parallel. 216 constraint_dependency: set 217 A set of instruction pairs that are found conflicted 218 due to the hardware constraints. 219 Because of this, they are executed in different cycles. 220 This set is used to add this dependency to the graph 221 in another method. 222 """ 223 # The method will destruct the graph, therefore we make a copy. 224 graph = deepcopy(self.nodes) 225 cycles_list = [] 226 available_nodes = list(self.start) # a list of available instructions 227 # pairs of instructions that are limited by hardware constraint 228 constraint_dependency = set() 229 230 while available_nodes: 231 if random: 232 shuffle(available_nodes) 233 if priority: 234 available_nodes.sort(key=cmp_to_key(self._compare_priority)) 235 current_cycle = [] 236 if apply_constraint is None: # if no constraits 237 current_cycle = deepcopy(available_nodes) 238 else: # check if constraits allow the parallelization 239 for node1 in available_nodes: 240 approval = True 241 for node2 in current_cycle: 242 if not apply_constraint(node1, node2, graph): 243 approval = False 244 # save the conflicted pairs of instructions 245 constraint_dependency.add((node2, node1)) 246 if approval: 247 current_cycle.append(node1) 248 # add this cycle to cycles_list 249 cycles_list.append(current_cycle) 250 251 # update the list of available nodes 252 # remove the executed nodes from available_node 253 for node in current_cycle: 254 available_nodes.remove(node) 255 # add new nodes to available_nodes 256 # if they have no other predecessors 257 for node in current_cycle: 258 for successor_ind in graph[node].successors: 259 graph[successor_ind].predecessors.remove(node) 260 if not graph[successor_ind].predecessors: 261 available_nodes.append(successor_ind) 262 graph[node].successors = set() 263 264 return cycles_list, constraint_dependency 265 266 def compute_distance(self, cycles_list): 267 """ 268 Compute the longest distance of each node 269 to the start and end nodes. 270 The weight for each dependency arrow is 271 the duration of the source instruction 272 (which should be 1 for gates schedule). 273 The method solves the longest path problem 274 by using the topological order in cycles_list. 275 It makes sure that by following the list, 276 the distance to the predecessors (successors) of 277 the source (target) node is always calculated 278 before the target (source) node. 279 280 Parameters 281 ---------- 282 cycles_list: list 283 A `cycles_list` obtained by the method `find_topological_order`. 284 """ 285 cycles_list = deepcopy(cycles_list) 286 287 # distance to the start node 288 for cycle in cycles_list: 289 for ind in cycle: 290 if not self.nodes[ind].predecessors: 291 self.nodes[ind].distance_to_start = \ 292 self.nodes[ind].duration 293 else: 294 self.nodes[ind].distance_to_start = max( 295 [ 296 self.nodes[predecessor_ind].distance_to_start 297 for predecessor_ind 298 in self.nodes[ind].predecessors 299 ] 300 ) + self.nodes[ind].duration 301 302 # distance to the end node 303 cycles_list.reverse() 304 self.reverse_graph() 305 for cycle in cycles_list: 306 for ind in cycle: 307 if not self.nodes[ind].predecessors: 308 self.nodes[ind].distance_to_end = self.nodes[ind].duration 309 else: 310 self.nodes[ind].distance_to_end = max( 311 [ 312 self.nodes[predecessor_ind].distance_to_end 313 for predecessor_ind 314 in self.nodes[ind].predecessors 315 ] 316 ) + self.nodes[ind].duration 317 self.longest_distance = max( 318 [self.nodes[i].distance_to_end for i in self.end]) 319 self.reverse_graph() 320 321 def _compare_priority(self, ind1, ind2): 322 """ 323 The node with longer `distance_to_end` has higher priority. 324 If it is the same for the two nodes, 325 the node with shorter `distance_to_start` has higher priority. 326 If node1 has higher priority, the method returns a negative value. 327 328 Parameters 329 ---------- 330 ind1, ind2: int 331 Indices of nodes. 332 """ 333 if self.nodes[ind1].distance_to_end == \ 334 self.nodes[ind2].distance_to_end: 335 # lower distance_to_start, higher priority 336 return self.nodes[ind1].distance_to_start - \ 337 self.nodes[ind2].distance_to_start 338 else: 339 # higher distance_to_end, higher priority 340 return self.nodes[ind2].distance_to_end - \ 341 self.nodes[ind1].distance_to_end 342 343 def add_constraint_dependency(self, constraint_dependency): 344 """ 345 Add the dependency caused by hardware constraint to the graph. 346 347 Parameters 348 ---------- 349 constraint_dependency: list 350 `constraint_dependency` obtained by the method 351 `find_topological_order`. 352 """ 353 for ind1, ind2 in constraint_dependency: 354 self.nodes[ind1].successors.add(ind2) 355 self.nodes[ind2].predecessors.add(ind1) 356 357 # Update the start and end nodes of the graph 358 start = [] 359 end = [] 360 for i, instruction in enumerate(self.nodes): 361 if not instruction.successors: 362 end.append(i) 363 if not instruction.predecessors: 364 start.append(i) 365 self.start = start 366 self.end = end 367 368 369class Scheduler(): 370 """ 371 A gate (pulse) scheduler for quantum circuits (instructions). 372 It schedules a given circuit or instructions 373 to reduce the total execution time by parallelization. 374 It uses heuristic methods mainly from 375 in https://doi.org/10.1117/12.666419. 376 377 The scheduler includes two methods, 378 "ASAP", as soon as possible, and "ALAP", as late as possible. 379 The later is commonly used in quantum computation 380 because of the finite lifetime of qubits. 381 382 The scheduler aims at pulse schedule and 383 therefore does not consider merging gates to reduce the gates number. 384 It assumes that the input circuit is optimized at the gate level 385 and matches the hardware topology. 386 387 Parameters 388 ---------- 389 method: str 390 "ASAP" for as soon as possible. 391 "ALAP" for as late as possible. 392 constraint_functions: list, optional 393 A list of hardware constraint functions. 394 Default includes a function `qubit_contraint`, 395 i.e. one qubit cannot be used by two gates at the same time. 396 """ 397 def __init__(self, method="ALAP", constraint_functions=None): 398 self.method = method 399 if constraint_functions is None: 400 self.constraint_functions = [qubit_constraint] 401 else: 402 return constraint_functions 403 404 def schedule(self, circuit, gates_schedule=False, 405 return_cycles_list=False, random_shuffle=False, 406 repeat_num=0): 407 """ 408 Schedule a `QubitCircuit`, 409 a list of `Gates` or a list of `Instruction`. 410 For pulse schedule, the execution time for each `Instruction` 411 is given in its `duration` attributes. 412 413 The scheduler first generates a quantum gates dependency graph, 414 containing information about 415 which gates have to be executed before some other gates. 416 The graph preserves the mobility of the gates, 417 i.e. commuting gates are not dependent on each other, 418 even if they use the same qubits. 419 Next, it computes the longest distance of each node 420 to the start and end nodes. 421 The distance for each dependency arrow is defined 422 by the execution time of the instruction 423 (By default, it is 1 for all gates). 424 This is used as a priority measure in the next step. 425 The gate with a longer distance to the end node and 426 a shorter distance to the start node has higher priority. 427 In the last step, it uses a list-schedule algorithm 428 with hardware constraint and priority and 429 returns a list of cycles for gates/instructions. 430 431 For pulse schedule, an additional step is required 432 to compute the start time of each instruction. 433 It adds the additional dependency 434 caused by hardware constraint to the graph 435 and recomputes the distance of each node to the start and end node. 436 This distance is then converted to 437 the start time of each instruction. 438 439 Parameters 440 ---------- 441 circuit: QubitCircuit or list 442 For gate schedule, 443 it should be a QubitCircuit or a list of Gate objects. 444 For pulse schedule, it should be a list of Instruction objects, 445 each with an attribute `duration` 446 that indicates the execution time of this instruction. 447 gates_schedule: bool, optional 448 `True`, if only gates schedule is needed. 449 This saves some computation 450 that is only useful to pulse schedule. 451 If the input `circuit` is a `QubitCircuit`, 452 it will be assigned to `True` automatically. 453 Otherwise, the default is `False`. 454 return_cycles_list: bool, optional 455 If `True`, the method returns the `cycles_list`, 456 e.g. [{0, 2}, {1, 3}], 457 which means that the first cycle contains gates0 and gates2 458 while the second cycle contains gates1 and gates3. 459 It is only usefull for gates schedule. 460 random_shuffle: bool, optional 461 If the commuting gates are randomly scuffled to explore 462 larger search space. 463 repeat_num: int, optional 464 Repeat the scheduling several times and use the best result. 465 Used together with ``random_shuffle=Ture``. 466 467 Returns 468 ------- 469 gate_cycle_indices or instruction_start_time: list 470 The cycle indices for each gate or 471 the start time for each instruction. 472 473 Examples 474 -------- 475 >>> from qutip.qip.circuit import QubitCircuit 476 >>> from qutip.qip.scheduler import Scheduler 477 >>> circuit = QubitCircuit(7) 478 >>> circuit.add_gate("SNOT", 3) # gate0 479 >>> circuit.add_gate("CZ", 5, 3) # gate1 480 >>> circuit.add_gate("CZ", 4, 3) # gate2 481 >>> circuit.add_gate("CZ", 2, 3) # gate3 482 >>> circuit.add_gate("CZ", 6, 5) # gate4 483 >>> circuit.add_gate("CZ", 2, 6) # gate5 484 >>> circuit.add_gate("SWAP", [0, 2]) # gate6 485 >>> 486 >>> scheduler = Scheduler("ASAP") 487 >>> scheduler.schedule(circuit, gates_schedule=True) 488 [0, 1, 3, 2, 2, 3, 4] 489 490 The result list is the cycle indices for each gate. 491 It means that the circuit can be executed in 5 gate cycles: 492 ``[gate0, gate1, (gate3, gate4), (gate2, gate5), gate6]`` 493 Notice that gate3 and gate4 commute with gate2, 494 therefore, the order is changed to reduce the number of cycles. 495 """ 496 circuit = deepcopy(circuit) 497 if repeat_num > 0: 498 random_shuffle = True 499 result = [0] 500 max_length = 4294967296 501 for i in range(repeat_num): 502 gate_cycle_indices = self.schedule( 503 circuit, gates_schedule=gates_schedule, 504 return_cycles_list=return_cycles_list, 505 random_shuffle=random_shuffle, repeat_num=0) 506 current_length = max(gate_cycle_indices) 507 if current_length < max_length: 508 result = gate_cycle_indices 509 max_length = current_length 510 return result 511 512 if isinstance(circuit, QubitCircuit): 513 gates = circuit.gates 514 else: 515 gates = circuit 516 517 # Generate the quantum operations dependency graph. 518 instructions_graph = InstructionsGraph(gates) 519 instructions_graph.generate_dependency_graph( 520 commuting=self.commutation_rules) 521 if self.method == "ALAP": 522 instructions_graph.reverse_graph() 523 524 # Schedule without hardware constraints, then 525 # use this cycles_list to compute the distance. 526 cycles_list, _ = instructions_graph.find_topological_order( 527 priority=False, apply_constraint=None, random=random_shuffle) 528 instructions_graph.compute_distance(cycles_list=cycles_list) 529 530 # Schedule again with priority and hardware constraint. 531 cycles_list, constraint_dependency = \ 532 instructions_graph.find_topological_order( 533 priority=True, apply_constraint=self.apply_constraint, 534 random=random_shuffle) 535 536 # If we only need gates schedule, we can output the result here. 537 if gates_schedule or return_cycles_list: 538 if self.method == "ALAP": 539 cycles_list.reverse() 540 if return_cycles_list: 541 return cycles_list 542 gate_cycles_indices = [0] * len(gates) 543 for cycle_ind, cycle in enumerate(cycles_list): 544 for instruction_ind in cycle: 545 gate_cycles_indices[instruction_ind] = cycle_ind 546 return gate_cycles_indices 547 548 # For pulse schedule, 549 # we add the hardware dependency to the graph 550 # and compute the longest distance to the start node again. 551 # The longest distance to the start node determines 552 # the start time of each pulse. 553 instructions_graph.add_constraint_dependency(constraint_dependency) 554 instructions_graph.compute_distance(cycles_list=cycles_list) 555 556 # Output pulse schedule result. 557 instruction_start_time = [] 558 if self.method == "ASAP": 559 for instruction in instructions_graph.nodes: 560 instruction_start_time.append( 561 instruction.distance_to_start - instruction.duration) 562 elif self.method == "ALAP": 563 for instruction in instructions_graph.nodes: 564 instruction_start_time.append( 565 instructions_graph.longest_distance - 566 instruction.distance_to_start) 567 return instruction_start_time 568 569 def commutation_rules(self, ind1, ind2, instructions): 570 """ 571 Determine if two gates commute, given that their used qubits overlap. 572 Since usually the input gates are already in a universal gate sets, 573 it uses an oversimplified condition: 574 575 If the two gates do not have the same name, 576 they are considered as not commuting. 577 If they are the same gate and have the same controls or targets, 578 they are considered as commuting. 579 E.g. `CNOT 0, 1` commute with `CNOT 0, 2`. 580 """ 581 instruction1 = instructions[ind1] 582 instruction2 = instructions[ind2] 583 if instruction1.name != instruction2.name: 584 return False 585 if (instruction1.controls) and \ 586 (instruction1.controls == instruction2.controls): 587 return True 588 elif instruction1.targets == instruction2.targets: 589 return True 590 else: 591 return False 592 593 def apply_constraint(self, ind1, ind2, instructions): 594 """ 595 Apply hardware constraint to check 596 if two instructions can be executed in parallel. 597 598 Parameters 599 ---------- 600 ind1, ind2: int 601 indices of the two instructions 602 instructions: list 603 The instruction list 604 """ 605 result = [] 606 for constraint_function in self.constraint_functions: 607 result.append(constraint_function(ind1, ind2, instructions)) 608 return all(result) 609 610 611def qubit_constraint(ind1, ind2, instructions): 612 """ 613 Determine if two instructions have overlap in the used qubits. 614 """ 615 if instructions[ind1].used_qubits & instructions[ind2].used_qubits: 616 return False 617 else: 618 return True 619