Optimal Scheduling of Graph States via Path Decompositions
arXiv:2403.04126 · doi:10.1103/PhysRevA.111.012627
Abstract
We study the optimal scheduling of graph states in measurement-based quantum computation, establishing an equivalence between measurement schedules and path decompositions of graphs. We define the spatial cost of a measurement schedule based on the number of simultaneously active qubits and prove that an optimal measurement schedule corresponds to a path decomposition of minimal width. Our analysis shows that approximating the spatial cost of a graph is -hard, while for graphs with bounded spatial cost, we establish an efficient algorithm for computing an optimal measurement schedule.
5 pages, 2 figures, published version
References in corpus (15)
- Fault-tolerant quantum computation by anyons
- Surface codes: Towards practical large-scale quantum computation
- Measurement-based quantum computation with cluster states
- Quantum Error Correction for Quantum Memories
- Fault-tolerant quantum computation with high threshold in two dimensions
- Roads towards fault-tolerant universal quantum computation
- Simulating quantum computation by contracting tensor networks
- A fault-tolerant one-way quantum computer
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Magic State Distillation: Not as Costly as You Think
- Entangling logical qubits with lattice surgery
- A measurement-based variational quantum eigensolver
- Lattice Surgery Translation for Quantum Computation
- Compilation of algorithm-specific graph states for quantum circuits
- Applications and resource reductions in measurement-based variational quantum eigensolvers