Complexity of graph-state preparation by Clifford circuits

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>G</mml:mi> <mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo> </mml:math> as the minimum number of two-qubit Clifford operations required to generate <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>G</mml:mi> <mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo> </mml:math> from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mn>0</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>&amp;#x2297;</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>s</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:math> for some <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>s</mml:mi> <mml:mo>&amp;#x2265;</mml:mo> <mml:mn>0</mml:mn> </mml:math> . 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, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>G</mml:mi> <mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo> </mml:math> can be generated from another graph state <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>H</mml:mi> <mml:mo fence="false" stretchy="false">&amp;#x27E9;</mml:mo> </mml:math> by an algorithm of CZ-complexity at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> if and only if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> can be obtained from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> by vertex deletions, local complementations and at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> vertices and rank-width <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>r</mml:mi> </mml:math> , the CZ-complexity is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>r</mml:mi> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , and if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is connected then it is at least <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>r</mml:mi> <mml:mo>&amp;#x2212;</mml:mo> <mml:mn>2</mml:mn> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>log</mml:mi> <mml:mo>&amp;#x2061;</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:math> , respectively.