Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1805.05305 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences

Transforming graph states using single-qubit operations

Axel Dahlberg, Stephanie Wehner

Published May 28, 2018• 51 citations
arXivHTMLPDF

Abstract

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’.

DOI
10.1098/rsta.2017.0325

Related papers

How to transform graph states using single-qubit operations: computational complexity and algorithms

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Abstract Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G⟩ can be transformed into another graph state |G′⟩ using LC + LPM + CC is N P -complete, which was previously not known. We also show that the problem remains NP-complete even if |G′⟩ is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G⟩ can be transformed to another graph state |G′⟩ is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G′ is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is N P -complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.

arXiv:1805.05306•Quantum Science and Technology•Jul 20, 2020•6 citations

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

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 $\widetilde O(n^{6.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 $\widetilde O(n^5)$ 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.

quant-pharXiv:2610.00527•Oct 2, 2026•0 citations

How to transform graph states using single-qubit operations: Computational complexity and algorithms

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G) can be transformed into another graph state |G) using LC + LPM + CC is NP-complete, which was previously not known. We also show that the problem remains NP-complete even if |G) is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G) can be transformed to another graph state |G) is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G' is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is NP-complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.

•Jan 1, 2020•29 citations

Quantum Graph-State Synthesis with SAT

Sebastiaan Brand, Tim J. Coopmans, Alfons Laarman

In quantum computing and quantum information processing, graph states are a specific type of quantum states which are commonly used in quantum networking and quantum error correction. A recurring problem is finding a transformation from a given source graph state to a desired target graph state using only local operations. Recently it has been shown that deciding transformability is already NP-hard. In this paper, we present a CNF encoding for both local and non-local graph state operations, corresponding to one- and two-qubit Clifford gates and single-qubit Pauli measurements. We use this encoding in a bounded-model-checking set-up to synthesize the desired transformation. Additionally, for a completeness threshold on local transformations, we provide an upper bound on the length of the transformation if it exists. We evaluate the approach in two settings: the first is the synthesis of the ubiquitous GHZ state from a random graph state where we can vary the number of qubits, while the second is based on a proposed 14 node quantum network. We find that the approach is able to synthesize transformations for graphs up to 17 qubits in under 30 minutes.

arXiv:2309.03593•Sep 7, 2023•0 citations

Asymptotic entanglement in circle stabilizer states and states forbidding arbitrary vertex-minors

Kenneth Goodenough, Marcelo Sales

Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state $|ψ\rangle$ can be transformed into another stabilizer state $|φ\rangle$ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that $|φ\rangle$ is a vertex-minor of $|ψ\rangle$. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state $|φ\rangle$, the entanglement in stabilizer states $|ψ\rangle$ that do not contain $|φ\rangle$ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected $|ψ\rangle$ not containing $|φ\rangle$ as a vertex-minor grows as $O(\log n)$, and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on $4$-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.

quant-pharXiv:2608.21526•Aug 25, 2026•0 citations

Local multi-qubit Clifford equivalence of graph states

Constantijn Molengraaf

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).

•Jan 1, 2019•0 citations
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’.
Abstract Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G⟩ can be transformed into another graph state |G′⟩ using LC + LPM + CC is N P -complete, which was previously not known. We also show that the problem remains NP-complete even if |G′⟩ is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G⟩ can be transformed to another graph state |G′⟩ is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G′ is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is N P -complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.
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 nnn labelled vertices in O~(n6.38)\widetilde O(n^{6.38})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)\widetilde O(n^5)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 are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC + LPM + CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. This question is of interest for effective routing or state preparation decisions in a quantum network or distributed quantum processor and also in the design of quantum repeater schemes and quantum error-correction codes. We first show that deciding whether a graph state |G) can be transformed into another graph state |G) using LC + LPM + CC is NP-complete, which was previously not known. We also show that the problem remains NP-complete even if |G) is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph state |G) can be transformed to another graph state |G) is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G' is a vertex-minor of a graph G. The computational complexity of the vertex-minor problem was prior to this paper an open question in graph theory. We prove that the vertex-minor problem is NP-complete by relating it to a new decision problem on 4-regular graphs which we call the semi-ordered Eulerian tour problem.
In quantum computing and quantum information processing, graph states are a specific type of quantum states which are commonly used in quantum networking and quantum error correction. A recurring problem is finding a transformation from a given source graph state to a desired target graph state using only local operations. Recently it has been shown that deciding transformability is already NP-hard. In this paper, we present a CNF encoding for both local and non-local graph state operations, corresponding to one- and two-qubit Clifford gates and single-qubit Pauli measurements. We use this encoding in a bounded-model-checking set-up to synthesize the desired transformation. Additionally, for a completeness threshold on local transformations, we provide an upper bound on the length of the transformation if it exists. We evaluate the approach in two settings: the first is the synthesis of the ubiquitous GHZ state from a random graph state where we can vary the number of qubits, while the second is based on a proposed 14 node quantum network. We find that the approach is able to synthesize transformations for graphs up to 17 qubits in under 30 minutes.
Stabilizer states play a central role in quantum information theory, and understanding their entanglement has motivated a large body of work. A well-studied question in particular is when a stabilizer state ∣ψ⟩|ψ\rangle∣ψ⟩ can be transformed into another stabilizer state ∣φ⟩|φ\rangle∣φ⟩ using only single-qubit Clifford operations and Pauli measurements. If this is possible, we say that ∣φ⟩|φ\rangle∣φ⟩ is a vertex-minor of ∣ψ⟩|ψ\rangle∣ψ⟩. Assuming Geelen's weak structural conjecture on vertex-minors, we establish the following general statement. For any fixed stabilizer state ∣φ⟩|φ\rangle∣φ⟩, the entanglement in stabilizer states ∣ψ⟩|ψ\rangle∣ψ⟩ that do not contain ∣φ⟩|φ\rangle∣φ⟩ as a vertex-minor is asymptotically constrained. More concretely, we show that the distance of any sufficiently rank-connected ∣ψ⟩|ψ\rangle∣ψ⟩ not containing ∣φ⟩|φ\rangle∣φ⟩ as a vertex-minor grows as O(log⁡n)O(\log n)O(logn), and prove similar results for the so-called locally accessible information, a quantity that captures the amount of information that can be learned through single-qubit Pauli measurements. Our results rely on (i) connecting the above two entanglement measures to rank functions of multimatroids, (ii) connecting the rank functions of circle stabilizer states to rank functions on 444-regular multigraphs, which asymptotically constrains the entanglement of circle stabilizer states, and (iii) using Geelen's weak structural conjecture on vertex-minors to `lift' the previous result to sufficiently connected states in proper vertex-minor-closed families of stabilizer states. Our results establish a connection between asymptotic stabilizer entanglement and forbidden vertex-minors, with direct implications for the entanglement that can be generated in quantum devices.
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).