2024/02/08 by Soh Kumabe, Ryuhei Mori, Kumabe, Soh +3 · 2 voices · 5 citations
Computer Science · Materials Science · #Machine Learning in Materials Science #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata
paper · pdf · doi:10.22331/q-2026-07-18-2165
Quantum 10, 2165 (2026). https://doi.org/10.22331/q-2026-07-18-2165 In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state |G⟩ as the minimum number of two-qubit Clifford operations required to generate |G⟩ from |0⟩⊗ (n+s) for some s≥ 0. Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, |G⟩ can be generated from another graph state |H⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r, the CZ-complexity is O(rn), and if G is connected then it is at least n+r-2. We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O(n) and O(nlog n), respectively.