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