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 ( r n ) , 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 ( n log n ) , respectively.
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 ( r n ) , 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 ( n log n ) , respectively.
Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool—for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G ′ is a vertex-minor of another graph G . The vertex-minor problem is, in general, -Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time O (| G | 3 ), where | G | is the size of the graph G , whenever the rank-width of G and the size of G ′ are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information. This article is part of a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’.
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on n labelled vertices in O(n6.38) bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost O(n5) bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this manuscript a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
We introduce a new notion of distance between two graph states ∣G⟩ and ∣G′⟩ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state ∣G⟩ from which both ∣G⟩ and ∣G′⟩ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems.
Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state ∣G⟩. The ancilla integrity problem asks, given a graph G and integer k, for the minimum -- over all graph states ∣G′⟩ with distance at most k from ∣G⟩ -- of the maximum component size of G′. Up to a factor of 2 in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between G and G′ is instead the minimum rank of the sum of their adjacency matrices over GF(2). We prove that rank integrity is XP parameterized by k. We also prove the complementary hardness result that rank integrity is W[1]-hard in k. Finally, we give an explicit O(n6)-time algorithm for ancilla integrity when G has n vertices and k=1.
In the range of applications opened by quantum technology, often a highly entangled source state is needed as an input for a protocol (target state). The easiest example of such an application is QKD, other examples are quantum secret sharing and measurement based quantum computing. Generating a non-local entangled state is however not trivial. Let us assume that there is an entangled state (source state) present in the network before the start of the protocol. One can ask than whether this source state can be transformed to the target state with only local operations. Local operations usually have a lower error rate compared to non-local operations. As the set of all quantum states increases exponentially, we will restrict ourselves to graph states (quantum states described by a simple graph). This allows one to study the graphs and local operations in a graph theory perspective, instead of in a quantum information perspective. In this thesis we investigate the complexity of deciding equivalence of two graph states under local multi-qubit operations (T-LMQC-equivalent), where T refers to the partition denoting which qubits are on the same device which allows multi-qubit operations. When T consist only of single qubit nodes, this problem reduces to the single qubit Clifford equivalence problem (SQC-EQUIV). It is known that SQC-EQUIV can be solved in O(N^4). On the other side, if all qubits are in the same node, the problem can be solved in O(1) as every source state can be transformed to any graph state on the same vertex set. We will present three algorithms to solve T-LMQC equivalence. The first algorithm solves the problem in general but the running time scales exponentially in the number of multi-qubit nodes and the size of the graph. The other two scale polynomially in the size of the graph, but do not allow for nodes with more than 2 qubits. The remaining question is indeed whether deciding T-LMQC equivalence is an easy (in P) problem or a hard problem (NP-complete).