Type-Based Verification of Connectivity Constraints in Lattice Surgery
Open Access
- 28 October 2024
- book chapter
- Published by Springer Nature
- p. 216-237
Abstract
Fault-tolerant quantum computation using lattice surgery can be abstracted as operations on graphs, wherein each logical qubit corresponds to a vertex of the graph, and multi-qubit measurements are accomplished by connecting the vertices with paths between them. Operations attempting to connect vertices without a valid path will result in abnormal termination. As the permissible paths may evolve during execution, it is necessary to statically verify that the execution of a quantum program can be completed. This paper introduces a type-based method to statically verify that well-typed programs can be executed without encountering halts induced by surgery operations. Alongside, we present $$\mathcal {Q}_{LS}$$ , a first-order quantum programming language to formalize the execution model of surgery operations. Furthermore, we provide a type checking algorithm by reducing the type checking problem to the offline dynamic connectivity problem.
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Logical quantum processor based on reconfigurable atom arraysNature, 2023
- Suppressing quantum errors by scaling a surface code logical qubitNature, 2023
- Realizing repeated quantum error correction in a distance-three surface codeNature, 2022
- Entangling logical qubits with lattice surgeryNature, 2021
- Surface code quantum computing by lattice surgeryNew Journal of Physics, 2012
- Interacting Quantum Observables2008
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- Maintaining minimum spanning trees in dynamic graphs1997
- Singleton, union and intersection types for program extractionLecture Notes in Computer Science, 1991
- The steiner problem in graphsNetworks, 1971