Quantum Circuit Optimization for Linear Nearest Neighbor Architectures

Optimization of Quantum Circuits for Interaction Distance in Linear Nearest Neighbor Architectures Alireza Shafaei, Mehdi Saeedi, Massoud Pedram University of Southern California Department of Electrical Engineering http://atrak.usc.edu/ Supported by the IARPA Quantum Computer Science

Outline Quantum Computing Geometric Constraints Linear Nearest Neighbor Proposed Solution Results OUTLINE | 1

Quantum Computing Motivation: Faster Algorithms Shor s factoring algorithm (Superpolynomial) Grover s search algorithm (Polynomial) Quantum walk on binary welded trees (Superpolynomial) Pell's equation (Superpolynomial) Formula evaluation (Polynomial) Quantum Algorithm Quantum Circuit Physical Realization QUANTUM COMPUTING | 2

Quantum Circuits Qubits Data is carried out by quantum bits or qubits Physical Object: ions, photons, etc. X H Quantum Gates Single-qubit: H (Hadamard gate), X (NOT gate) Two-qubit: CNOT (Controlled NOT), SWAP q0 q0 q1 q0 q1 q0 q1 Quantum Circuit q1 q0 X q0 q1 q2 q3 QUANTUM COMPUTING | 3

Physical Realization Quantum Computing Technologies Ion-Trap Superconducting Photonics Neutral Atoms Quantum Dots CNOT X CNOT X CNOT q0 q1 q2 q3 q4 QUANTUM COMPUTING | 4

Geometric Constraints Limited Interaction Distance Nearest Neighbor Architectures Adjacent qubits can be involved in a two-qubit gate Distant Qubits Route qubits to make them adjacent Move-based Move instruction, routing channel SWAP-based Insert SWAP gates 2 3 1 1 2 3 1 2 3 1 4 4 1 Objective: Minimize the # of SWAP gates GEOMETRIC CONSTRAINTS | 5

Limited Interaction Distance Non-local circuit Local circuit How to create a local circuit? 1. Insert SWAP gates 2. Change the qubit ordering (i.e., qubit placement) SWAP-free! GEOMETRIC CONSTRAINTS | 6

Proposed Solution 3 5 Interaction Graph 1 4 Inter-set SWAP gates 2 6 Find SWAP-free sets: Select 2-qubit gates one by one until following conditions are met on the corresponding interaction graph ?: - ? 2, and - there is no cycle in ?. SWAP-free Set PROPOSED SOLUTION | 7

Proposed Solution ISi: inter-set SWAP gates Gi: set of 2-qubit gates that form a Path (SWAP-free) Pi: qubit ordering qubits G1 IS1 G2 IS2 ISK-1 GK P1 P1 P2 P2 P3 PK-1 Pk PK Qubit placements dynamically change Look-ahead search in order to find the placement that minimizes the number of inter-set SWAP gates Future work Force-directed placement PROPOSED SOLUTION | 8

Results Number of SWAP gates Circuit 3_17_13 4_49_17 4gt10-v1_81 4gt11_84 4gt12-v1_89 4gt13-v1_93 4gt4-v0_80 4gt5_75 4mod5-v1_23 4mod7-v0_95 aj-e11_165 alu-v4_36 decod24-v3_46 ham7_104 hwb4_52 hwb5_55 hwb6_58 hwb7_62 n 3 4 5 5 5 5 5 5 5 5 4 5 4 7 4 5 6 7 [18] 6 20 30 3 35 11 34 17 16 28 39 23 4 84 14 79 136 3660 Ours 4 12 20 1 35 6 34 12 9 21 36 18 3 68 10 63 118 2128 % 33 40 33 67 0 45 0 29 44 25 8 22 25 19 29 20 13 42 Circuit hwb8_118 hwb9_123 mod5adder_128 mod8-10_177 rd32-v0_67 rd53_135 rd73_140 sym9_148 sys6-v0_144 urf1_149 urf2_152 urf5_158 QFT5 QFT6 QFT7 QFT8 QFT9 QFT10 n 8 9 6 5 4 7 10 10 10 9 8 9 5 6 7 8 9 10 [18] 24541 36837 85 77 2 76 62 5480 62 60235 25502 52440 12 22 39 60 87 123 Ours 14361 21166 51 72 2 66 56 3415 59 44072 17670 39309 6 12 26 33 54 70 % 41 43 40 6 0 13 10 38 5 27 31 25 50 45 33 45 38 43 [18] M. Saeedi, R. Wille, and R. Drechsler, Synthesis of quantum circuits for linear nearest neighbor architectures, QIP, 10 (3): 355-377, 2011. RESULTS | 9

Results Improvement over [18] 80 70 60 50 40 28 30 20 10 0 28% on average improvement [18] M. Saeedi, R. Wille, and R. Drechsler, Synthesis of quantum circuits for linear nearest neighbor architectures, QIP, 10 (3): 355-377, 2011. RESULTS | 10

Thanks!