Dahlberg Axel, Wehner Stephanie
QuTech, Lorentzweg 1, 2628 CJ Delft, The Netherlands
QuTech, Lorentzweg 1, 2628 CJ Delft, The Netherlands.
Philos Trans A Math Phys Eng Sci. 2018 Jul 13;376(2123). doi: 10.1098/rsta.2017.0325.
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 ' is a of another graph The vertex-minor problem is, in general, [Formula: see text]-Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the which equals the 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 (||), where || is the size of the graph , whenever the rank-width of and the size of ' 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'.
稳定器状态构成量子信息中一类重要的状态，并且在量子纠错中至关重要。在此，我们提供一种算法，用于判定一个稳定器（目标）状态是否可通过单量子比特克利福德操作（LC）、单量子比特泡利测量（LPM）以及持有各个量子比特的位点之间的经典通信（CC）从另一个稳定器（源）状态获得。此外，我们给出一种方法来获取从源状态制备所需目标状态的LC + LPM + CC操作序列，并展示这些操作如何能够并行应用以在恒定时间内达到目标状态。我们的算法在量子网络、量子计算中有应用，并且还可作为一种设计工具——例如，用于找到量子纠错码之间的变换。我们提供了该算法的软件实现，使得这个工具更易于应用。促成我们算法的一个关键见解是表明该问题等同于图论中的一个问题，即判定某个图是否是另一个图的顶点子图。顶点子图问题通常是NP完全的，但在不太复杂的图上可以有效解决。图的复杂度的一种度量是秩宽，它等于一类称为图态的稳定器状态子类的秩，因此直观上是纠缠的一种度量。在此，我们表明只要图及其顶点子图的秩宽有界，顶点子图问题就可以在时间O(|G|)内解决，其中|G|是图G的大小。我们的算法基于Courcelle用于解决固定参数可处理问题的技术，这里相关的固定参数是秩宽。本文的后半部分作为对这些概念的易懂但远非详尽的介绍，可能对量子信息中的许多其他问题有用。本文是“量子力学基础及其对当代社会的影响”讨论会议文集的一部分。
