Surface Code Compilation via Edge-Disjoint Paths
We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit’s qubits in surface codes can result in long-range two-qubit o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2022-05-01
|
| Series: | PRX Quantum |
| Online Access: | http://doi.org/10.1103/PRXQuantum.3.020342 |
| _version_ | 1818552238080000000 |
|---|---|
| author | Michael Beverland Vadym Kliuchnikov Eddie Schoute |
| author_facet | Michael Beverland Vadym Kliuchnikov Eddie Schoute |
| author_sort | Michael Beverland |
| collection | DOAJ |
| description | We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit’s qubits in surface codes can result in long-range two-qubit operations across the grid. We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillae in constant depth that can be used to perform these long-range operations. This forms one core part of our edge-disjoint path compilation (EDPC) algorithm, by easily performing many parallel long-range Clifford operations in constant depth. It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint path problems. Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories. In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of EDPC. EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on swap gates and network coding. EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources. We implement EDPC and find significantly improved performance for circuits built from parallel controlled-not (cnot) gates, and for circuits that implement the multicontrolled X gate C^{k}NOT. |
| first_indexed | 2024-12-12T09:10:35Z |
| format | Article |
| id | doaj.art-4b2b60db2d41405e8ab5bce798281705 |
| institution | Directory Open Access Journal |
| issn | 2691-3399 |
| language | English |
| last_indexed | 2024-12-12T09:10:35Z |
| publishDate | 2022-05-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | PRX Quantum |
| spelling | doaj.art-4b2b60db2d41405e8ab5bce7982817052022-12-22T00:29:32ZengAmerican Physical SocietyPRX Quantum2691-33992022-05-013202034210.1103/PRXQuantum.3.020342Surface Code Compilation via Edge-Disjoint PathsMichael BeverlandVadym KliuchnikovEddie SchouteWe provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit’s qubits in surface codes can result in long-range two-qubit operations across the grid. We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillae in constant depth that can be used to perform these long-range operations. This forms one core part of our edge-disjoint path compilation (EDPC) algorithm, by easily performing many parallel long-range Clifford operations in constant depth. It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint path problems. Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories. In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of EDPC. EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on swap gates and network coding. EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources. We implement EDPC and find significantly improved performance for circuits built from parallel controlled-not (cnot) gates, and for circuits that implement the multicontrolled X gate C^{k}NOT.http://doi.org/10.1103/PRXQuantum.3.020342 |
| spellingShingle | Michael Beverland Vadym Kliuchnikov Eddie Schoute Surface Code Compilation via Edge-Disjoint Paths PRX Quantum |
| title | Surface Code Compilation via Edge-Disjoint Paths |
| title_full | Surface Code Compilation via Edge-Disjoint Paths |
| title_fullStr | Surface Code Compilation via Edge-Disjoint Paths |
| title_full_unstemmed | Surface Code Compilation via Edge-Disjoint Paths |
| title_short | Surface Code Compilation via Edge-Disjoint Paths |
| title_sort | surface code compilation via edge disjoint paths |
| url | http://doi.org/10.1103/PRXQuantum.3.020342 |
| work_keys_str_mv | AT michaelbeverland surfacecodecompilationviaedgedisjointpaths AT vadymkliuchnikov surfacecodecompilationviaedgedisjointpaths AT eddieschoute surfacecodecompilationviaedgedisjointpaths |