Cohomological framework for contextual quantum computations [Published December 2019]. We describe a cohomological framework for measurement based quantum computation, in which symmetry plays a central role. Therein, the essential information about the computational output is contained in topological invariants, namely elements of two cohomology groups. One of those invariants applies to the deterministic case, and the other to the general probabilistic case. The same invariants also witness quantumness in the form of contextuality. In result, they give rise to fundamental algebraic structures underlying quantum computation.
The Boolean algebra is at the foundation of all digital classical computation. From a quantum perspective it is thus pertinent to ask what its counterpart in quantum computation is. Which fundamental algebraic structures can quantum computation be based on? This is the question we are concerned with here. We address it for the model of measurement-based quantum computation (MBQC), in which the process of computation is driven by measurements rather than unitary evolution.
To address the above question, we introduce a generalized notion of MBQC based on symmetry. Each such H-MBQC transforms under a characteristic symmetry group H, whose action preserves the outputted function o. We establish the following properties.
The input structure to each H-MBQC is a group Q related to H. Denote by N the normal subgroup N of H, such that each element in it maps the measurable observables of the computation element-wise to themselves, up to sign. Then, it holds that Q=H/N.
The output function o is preserved under the action of H.
In the deterministic case, the output function o is determined by a 2-cocycle in the cohomology of chain complexes, and the action of Q on it. In the probabilistic case, the output function o is determined up to an additive constant by the phase function, a 1-cocycle in group cohomology that derives from the action of H on the set of measurable observables.
We impose as minimal requirements on our description of H-MBQCs that it contains (i) a witness of quantumness, and (ii) the computed function. It turns out that this information is topological. Namely, the witness of quantumness arises as a contextuality witness, provided by the above cohomological invariants. The same invariants also characterize the outputted function.
R. Raussendorf, Cohomological framework for contextual quantum computations, arXiv:1602:04155, Quant. Inf. Comp. 19, 1141 - 1170 (2019).
A computationally universal phase of quantum matter [Published March 4, 2019] We provide the first example of a symmetry protected quantum phase that has universal computational power. This two-dimensional phase is protected by one-dimensional line-like symmetries that can be understood in terms of local symmetries of a tensor network. These local symmetries imply that every ground state in the phase is a universal resource for measurement based quantum computation.
In the presence of symmetry, quantum phases of matter can have computational power. The important property is that the computational power is uniform. It does not depend on the precise choice of the state within the phase, and is thus a property of the phase itself. In this way, phases of quantum matter acquire a computational characterization and computational value.
Quantum computational power of physical phases is utilized by measurement based quantum computation (MBQC), where the process of computation is driven by local measurements on an initial entangled state. Here, we consider initial states that originate from symmetry protected topological phases. Work on the usefulness of SPT phases of matter for MBQC have to date been focussed on spatial dimension 1. Computationally, physical phases in dimension 2 and higher are more interesting than in dimension 1. The reason is that, in MBQC, one spatial dimension plays the role of circuit model time. Therefore, MBQC in dimension D corresponds to the circuit model in dimension D-1, and universal MBQC is possible only in D >=2.
Here, we prove the existence of a computationally universal phase of quantum matter in spatial dimension two. The phase we consider is protected by one-dimensional line-like symmetries, generalizing the conventional notion of symmetry protected topological order defined by global on-site symmetries. As in the case of global symmetries, these line symmetries can be built from the local symmetries of a tensor network which persist throughout the phase. Using this, we establish that computational universality persists throughout the entire phase.
Symmetry Lego. Ground states throughout the whole cluster states have an enhanced symmetry, and the functioning of MBQC is based on it. This symmetry is best under stood in terms of tensor networks. (a) Tensor network representing an MBQC resource state in the 2D cluster phase. Every local tensor represents one physical spin 1/2 particle. (b) Throughout the cluster phase, each local tensor is invariant under a number of symmetries. These symmetries form the backbone of measurement-based computation in the cluster phase, as is illustrated in Figs. (c) and (d). (c) The symmetries shown in (b) are composed into a larger pattern propagating a logical Z-operator forward in time. The area shown represents the ``clock cycle'' of the compution. If all physical qubits shown are measured in the X-eigenbasis, the resulting operation is the logical identity (computational wire). (d) If the qubit marked by the double-headed arrow is measured off the X-basis, the result is an entangling gate. Again, the functioning of the gate can be understood in terms of the tensor symmetries shown in (b).
R. Raussendorf, C. Okay, D.S. Wang, D.T. Stephen, H. Poulsen Nautrup, A computationally universal quantum phase of matter, Phys. Rev. Lett. 122, 090501 (2019).
Further computationally universal SPT phases, and the connection to quantum cellular automata: D.T. Stephen, H.P Nautrup, J. Bermejo-Vega, J. Eisert, R. Raussendorf, Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter, arXiv:1806.08780.
Computational power of symmetry protected topological phases [Published July 5, 2017] We consider ground states of quantum spin chains with symmetry-protected topological (SPT) order as resources for measurement-based quantum computation (MBQC). We show that, for a wide range of SPT phases, the computational power of ground states is uniform throughout each phase. This computational power, defined by the Lie group of executable gates in MBQC, is determined by the same algebraic information that labels the SPT phase itself. We prove that these Lie groups always contain a full set of single-qubit gates, thereby affirming the long-standing conjecture that general SPT phases can serve as computationally useful phases of matter.
Changeover from unitary evolution to measurement. For any (unique) ground state in a given SPT phase, the same set of logical unitaries and measurements can be implemented via MBQC on that state. Now, when is a logical unitary implemented, and when a measurement? -- This is decided by the interplay between (i) the basis for physical measurement implementing the logical operation and (ii) the number of repitions of that physical measurement along the spin chain. There is a preferred measurement basis, the so-called wire basis. If the spins of the chain are measured in this basis, the logical identity is implemented. For all other operations, one needs to deviate from the wire basis (Herein actually lies the difficulty of computing in SPT phases: away from the wire basis, the logical processing is a priori prone to decoherence, which needs to be circumvented.).
Parametrizing the deviation of the actual measurement basis from the wire basis by an angle alpha, and denoting the number of repitions of the measurement by N, the angle of the unitary rotation is Phi ~ alpha * N, and the deviations from unitarity are ~ alpha^2 * N. Therefore, the strategy to implement a unitary with rotation angle Phi is to choose alpha ~ Phi/N, with N large, and then repeat N times. The optimal strategy for a measurement is to choose alpha = Pi/4. However, for sufficiently large number N of repitions, all angles alpha <> 0 will result in a logical measurement. As per the above relation, the changeover occurs around alpha = 1/sqrt(N).
Now to the figure itself, which shows a numerical simulation of MBQC gate implementation. Here, the number of repitions of the physical measurement is N=1600. On the horizontal axis, the angle alpha is plotted. The vertical axis shows the fraction of outcomes "0" among the outcomes "0" or "1". Each point in the plot represents a sequence of 1600 repitions of the same physical measurement. We find that, for every angle alpha, the frequencies of obtaining "0" cluster around certain values. If alpha is small, there is -- up to noise -- only one value. Thus, the physical measurement does not learn anything about the processed logical state. The logical evolution is unitary. On the other hand, if alpha is large, there are several values around which the frequency N_0/N can cluster, corresponding to measurement of the logical state. As expected, the changeover occurs around alpha=1/sqrt(N).
For a detailed description of the computational scheme, demonstrating how to perform logical unitary gates and measurements, see Robert Raussendorf, Dong-Sheng Wang, Abhishodh Prakash, Tzu-Chieh Wei, and David T. Stephen, Symmetry-protected topological phases with uniform computational power in one dimension, Phys. Rev. A 96, 012302 (2017).
For the algebraic aspects and their implications, see David T. Stephen, Dong-Sheng Wang, Abhishodh Prakash, Tzu-Chieh Wei, and Robert Raussendorf, Computational Power of Symmetry-Protected Topological Phases, Phys. Rev. Lett. 119, 010504 (2017).
Contextuality and Wigner function negativity in qubit quantum computation. [Published May 17, 2017] We describe schemes of quantum computation with magic states on qubits for which contextuality and negativity of the Wigner function are necessary resources possessed by the magic states. These schemes satisfy a constraint. Namely, the non-negativity of Wigner functions must be preserved under all available measurement operations. Furthermore, we identify stringent consistency conditions on such computational schemes, revealing the general structure by which negativity of Wigner functions, hardness of classical simulation of the computation, and contextuality are connected.
Journal Reference: Robert Raussendorf, Dan E. Browne, Nicolas Delfosse, Cihan Okay, Juan Bermejo-Vega, Contextuality and Wigner-function negativity in qubit quantum computation, Phys. Rev. A 95, 052334 (2017).
State space for the one-qubit states. This plot illustrates the difference between positive Wigner functions and non-contextual hidden variable models. The physical states lie within or on the Bloch sphere (BS). The two tetrahedra contain the states positively represented by the Wigner functions W and W, respectively. The state space describable by a non-contextual HVM is a cube with corners (+/- 1, +/- 1, +/- 1). It contains the Bloch ball.
Wigner Function Negativity and Contextuality in Quantum Computation on Rebits. [Posted May 4, 2015] We describe a universal scheme of quantum computation by state injection on rebits (states with real density matrices). For this scheme, we establish contextuality and Wigner function negativity as computational resources, extending results of M. Howard et al. [Nature (London) 510, 351 (2014)] to two-level systems. For this purpose, we define a Wigner function suited to systems of multiple rebits and prove a corresponding discrete Hudson's theorem. We introduce contextuality witnesses for rebit states and discuss the compatibility of our result with state-independent contextuality.
Journal Reference: Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian, and Robert Raussendorf, Wigner Function Negativity and Contextuality in Quantum Computation on Rebits, Phys. Rev. X 5, 021003 (2015).
Negativity and contextuality for rebits. Left: Rebit Wigner function of a three-qubit graph state. This state is local unitary equivalent to a Greenberger-Horne-Zeilinger (GHZ) state. Negativity of the Wigner function for the three-qubit graph state indicates non-classicality. Contrary to qudits in odd prime dimension, for rebits negativity is not synonymous wit contextuality. Nevertheless, the negativity in the Wigner function for the three-qubit graph state is strong enough to witness contextuality. Right: From the perspective of contextuality in quantum computation with magic states, Mermin's square and star, and all their cousins, are ``little monsters''. For explanation, see below.
State-independent contextuality, as exhibited by Mermin's square and star, provides beautifully simple proofs for the Kochen-Specker theorem in dimension 4 and higher. However, for establishing contextuality as a resource only posessed by magic states, state-independent contextuality poses a problem: If ``cheap'' Pauli measurements already have contextuality, then how can one say that contextuality is a key resource provided by the magic states? For qudits, the problem doesn't exist because there is no state-independent contextuality w.r.t. Pauli measurements. For rebits, the problem is overcome by the operational restriction to CSS-ness preserving gates and measurements.
Contextuality in measurement-based quantum computation. [Published August 19, 2013] We show, under natural assumptions for qubit systems, that measurement-based quantum computations (MBQCs) which compute a nonlinear Boolean function with a high probability are contextual. The class of contextual MBQCs includes an example which is of practical interest and has a superpolynomial speedup over the best-known classical algorithm, namely, the quantum algorithm that solves the ``discrete log'' problem.
Journal Reference: Robert Raussendorf, Contextuality in measurement-based quantum computation, Phys. Rev. A 88, 022322 (2013).
Contextuality in measurement-based quantum computation. Explanation: MBQC stands for ``Measurement-based quantum computation''. The prefix ``l2'' means that the linear classical side-processing performed by the control computer is restricted to addition mod 2. The theorem displayed on the left shows that contextuality of MBQC extends to probabilistic such computations. The contextuality threshold is very close to 1 if no further constraint is placed on the function computed, apart from non-linearity. However, the contextuality threshold does strongly depend upon the computed function. For so-called bent functions, the contextuality threshold reaches 1/2 in the large-size limit. This means that probabilistic MBQC evaluation of bent functions is contextual even if the output of the computation is only a tiny bit biassed away from completely random output.
Experimental demonstration of topological error correction. [Posted June 7, 2012] Here we report the experimental demonstration of topological error correction with an eight-photon cluster state. We show that a correlation can be protected against a single error on any quantum bit. Also, when all quantum bits are simultaneously subjected to errors with equal probability, the effective error rate can be significantly reduced. Our work demonstrates the viability of topological error correction for fault-tolerant quantum information processing.
The present experiment uses an 8-qubit cluster state which shares topological features with its larger (potentially much larger) cousin, the three-dimensional cluster state. A 3D cluster state is for measurement-based quantum computation (MBQC) what the Kitaev surface code is for the circuit model: a fault-tolerant fabric in which protected quantum gates can be implemented in a topological fashion. The present experiment demonstrates the fault-tolerance properties, not yet the encoded quantum gates. For the latter, larger cluster states will be required in future experiments. The smallest possible setting to demonstrate topological error-correction with cluster states requires 8 qubits, which was just in reach of the present photon-based experiment.
Journal Reference: Xing-Can Yao et al, Experimental demonstration of topological error correction, Nature 482, 489 (2012).
Also see James D. Franson, Quantum computing: A topological route to error correction, Nature 482, News and Views, (2012).
Topological error correction with cluster states. (left) Measurement of the error in the topologically protected correlation of the cluster state (0: perfect correlation, 0.5: no correlation, 1: perfect anti-correlation), vs. the one qubit error rate. The local errors are subjected to the cluster state on purpose, with varying strength. The black curve is the theory prediction for the strength of the correlation vs local error rate, if no error correction is performed, and the red dashed curve is for the same correlation with error correction performed. The dots represent the measured data. For small error probabilities, topological error correction significantly reduces logical error. (right) What do the 8-qubit cluster state used in the experiment and a large 3D cluster state have in common? - Both can be described by an underlying three-dimensional chain complex. Their topological error protection derives from the homology properties of these complexes.
AKLT states as computational resources. [Posted February 24, 2011] We show that the ground state of an isotropic quantum antiferromagnet in two spatial dimensions, a so-called Affleck-Kennedy-Lieb-Tasaki (AKLT) state, is a universal resource for measurement-based quantum computation. This may become useful in two ways: (1) It may bring closer to experimental reality the possibility of creating computational resource states by cooling, and (2) More generally, it strengthens the overlap between the field of measurement-based quantum compuation and condensed matter physics. Could this overlap generate novel ideas and approaches for the classification of all computationally universal resource states?
An initial highly entangled resource state is the key ingredient in measurement-based quantum computation, where the process of computation itself is driven by single-spin measurements. Universal resource states are known to be rare. Recent quests for them have turned to ground states of short-ranged, preferably two-body interacting Hamiltonians, as they may be created by cooling. In particular, success has been obtained in the family of the AKLT models, in which single-qubit operations are shown to be possible. However, it remained open whether any state in the AKLT family can provide the full capability for universal quantum computation. Our results show that this is indeed the case for the two-dimensional spin-3/2 AKLT state supported on the honeycomb lattice.
The AKLT state was originally constructed in 1987 to understand the low-energy phenomenology of rotationally invariant spin Hamiltonians, a question at the center of condensed matter physics but outside the realm of quantum information. Amazingly, however, this happened not long after the notion of quantum computation started to develop, through the works of Feynman (1982) and Deutsch (1985).
[Journal Reference: Tzu-Chieh Wei, Ian Affleck, Robert Raussendorf, Physical Review Letters 106, 070501 (2011). An analogous result has been obtained independently by A. Miyake; See arXiv:1009.3491.]
AKLT states as universal computational resources. At the techical level, our constructions proceeds by reducing the 2D AKLT state to a 2D cluster state through local operations (POVMs and projective measurements). The 2D cluster is the standard universal resource. The mapping requires three steps. (1) We devise a suitable generalized local measurement (local POVM) which breaks the rotational symmetry of the AKLT state. (2) We show that the resulting state is an encoded graph state on a random planar graph. Therein, the planar graph depends on the random but short-range correlated POVM outcomes. The encoding can be undone by local measurements. (3) A planar graph state can be further reduced to a 2D cluster state if it is large and has traversing paths, i.e., is in the supercritical phase of percolation (a). We show that this is indeed the case for typical graph states resulting from the POVM in Step 1, by Monte-Carlo simulation (b).