Good dynamics versus bad kinematics: is entanglement needed for quantum computation?

Quantifying computational advantage of Grover's algorithm with the trace speed

Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.

Emulating Anyonic Fractional Statistical Behavior in a Superconducting Quantum Circuit

Anyons are exotic quasiparticles obeying fractional statistics, whose behavior can be emulated in artificially designed spin systems. Here we present an experimental emulation of creating anyonic excitations in a superconducting circuit that consists of four qubits, achieved by dynamically generating the ground and excited states of the toric code model, i.e., four-qubit Greenberger-Horne-Zeilinger states. The anyonic braiding is implemented via single-qubit rotations: a phase shift of π related to braiding, the hallmark of Abelian 1/2 anyons, has been observed through a Ramsey-type interference measurement.

Universal quantum computation with little entanglement

We show that universal quantum computation can be achieved in the standard pure-state circuit model while the entanglement entropy of every bipartition is small in each step of the computation. The entanglement entropy required for large-scale quantum computation even tends to zero. Moreover we show that the same conclusion applies to many entanglement measures commonly used in the literature. This includes e.g., the geometric measure, localizable entanglement, multipartite concurrence, squashed entanglement, witness-based measures, and more generally any entanglement measure which is continuous in a certain natural sense. These results demonstrate that many entanglement measures are unsuitable tools to assess the power of quantum computers.

Quantum information processing by nuclear magnetic resonance on quadrupolar nuclei

Nuclear magnetic resonance is viewed as an important technique for the implementation of many quantum information algorithms and protocols. Although the most straightforward approach is to use the two-level system composed of spin 1/2 nuclei as qubits, quadrupolar nuclei, which possess a spin greater than 1/2, are being used as an alternative. In this study, we show some unique features of quadrupolar systems for quantum information processing, with an emphasis on the ability to execute efficient quantum state tomography (QST) using only global rotations of the spin system, whose performance is shown in detail. By preparing suitable states and implementing logical operations by numerically optimized pulses together with the QST method, we follow the stepwise execution of Grover's algorithm. We also review some work in the literature concerning the relaxation of pseudo-pure states in spin 3/2 systems as well as its modelling in both the Redfield and Kraus formalisms. These data are used to discuss differences in the behaviour of the quantum correlations observed for two-qubit systems implemented by spin 1/2 and quadrupolar spin 3/2 systems, also presented in the literature. The possibilities and advantages of using nuclear quadrupole resonance experiments for quantum information processing are also discussed.

Positive phase space transformation incompatible with classical physics

Bell conjectured that a positive Wigner function does not allow violation of the inequalities imposed by local hidden variable theories. A requirement for this conjecture is "when phase space measurements are performed." We introduce the theory-independent concept of "operationally local transformations" which refers to the change of the switch on a local measurement apparatus. We show that two separated parties, performing only phase space measurements on a composite quantum system with a positive Wigner function and performing only operationally local transformations that preserve this positivity, can nonetheless violate Bell's inequality. Such operationally local transformations are realized using entangled ancillae.

Distributed quantum computing

Quantum computing and distributed systems may enter a mutually beneficial partnership in the future. On the one hand, it is much easier to build a number of small quantum computers rather than a single large one. On the other hand, the best results concerning some of the fundamental problems in distributed computing can potentially be dramatically improved upon by taking advantage of the superior resources and processing power that quantum mechanics offers. This survey has the purpose to highlight both of these benefits. We first review the current results regarding the implementation of arbitrary quantum algorithms on distributed hardware. We then discuss existing proposals for quantum solutions of leader election - a fundamental problem from distributed computing. Quantum mechanics allows leader election to be solved with no communication, provided that certain pre-shared entanglement is already in place. Further, an impossibility result from classical distributed computing is circumvented by the quantum solution of anonymous leader election - a unique leader is elected in finite time with certainty. Finally, we discuss the viability of these proposals from a practical perspective. Although, theoretically, distributed quantum computing looks promising, it is still unclear how to build quantum hardware and how to create and maintain robust large-scale entangled states. Moreover, it is not clear whether the costs of creating entangled states and working with them are smaller than the costs of existing classical solutions.

Demonstration of a compiled version of Shor's quantum factoring algorithm using photonic qubits

We report an experimental demonstration of a complied version of Shor's algorithm using four photonic qubits. We choose the simplest instance of this algorithm, that is, factorization of N=15 in the case that the period r=2 and exploit a simplified linear optical network to coherently implement the quantum circuits of the modular exponential execution and semiclassical quantum Fourier transformation. During this computation, genuine multiparticle entanglement is observed which well supports its quantum nature. This experiment represents an essential step toward full realization of Shor's algorithm and scalable linear optics quantum computation.

Knill-laflamme-milburn linear optics quantum computation as a measurement-based computation

We show that the Knill Lafllame Milburn method of quantum computation with linear optics gates can be interpreted as a one-way, measurement-based quantum computation of the type introduced by Briegel and Raussendorf. We also show that the permanent state of n n-dimensional systems is a universal state for quantum computation.

Limitations of quantum simulation examined by simulating a pairing Hamiltonian using nuclear magnetic resonance

Quantum simulation uses a well-known quantum system to predict the behavior of another quantum system. Certain limitations in this technique arise, however, when applied to specific problems, as we demonstrate with a theoretical and experimental study of an algorithm proposed by Wu, Byrd, and Lidar [Phys. Rev. Lett. 89, 057904 (2002).10.1103/PhysRevLett.89.057904] to find the low-lying spectrum of a pairing Hamiltonian. While the number of elementary quantum gates required scales polynomially with the size of the system, it increases inversely to the desired error bound E. Making such simulations robust to decoherence using fault tolerance requires an additional factor of approximately 1/E gates. These constraints, along with the effects of control errors, are illustrated using a three qubit NMR system.

Experimental one-way quantum computing

Standard quantum computation is based on sequences of unitary quantum logic gates that process qubits. The one-way quantum computer proposed by Raussendorf and Briegel is entirely different. It has changed our understanding of the requirements for quantum computation and more generally how we think about quantum physics. This new model requires qubits to be initialized in a highly entangled cluster state. From this point, the quantum computation proceeds by a sequence of single-qubit measurements with classical feedforward of their outcomes. Because of the essential role of measurement, a one-way quantum computer is irreversible. In the one-way quantum computer, the order and choices of measurements determine the algorithm computed. We have experimentally realized four-qubit cluster states encoded into the polarization state of four photons. We characterize the quantum state fully by implementing experimental four-qubit quantum state tomography. Using this cluster state, we demonstrate the feasibility of one-way quantum computing through a universal set of one- and two-qubit operations. Finally, our implementation of Grover's search algorithm demonstrates that one-way quantum computation is ideally suited for such tasks.

Efficient classical simulation of slightly entangled quantum computations

We present a classical protocol to efficiently simulate any pure-state quantum computation that involves only a restricted amount of entanglement. More generally, we show how to classically simulate pure-state quantum computations on n qubits by using computational resources that grow linearly in n and exponentially in the amount of entanglement in the quantum computer. Our results imply that a necessary condition for an exponential computational speedup (with respect to classical computations) is that the amount of entanglement increases with the size n of the computation, and provide an explicit lower bound on the required growth.

Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance

The number of steps any classical computer requires in order to find the prime factors of an l-digit integer N increases exponentially with l, at least using algorithms known at present. Factoring large integers is therefore conjectured to be intractable classically, an observation underlying the security of widely used cryptographic codes. Quantum computers, however, could factor integers in only polynomial time, using Shor's quantum factoring algorithm. Although important for the study of quantum computers, experimental demonstration of this algorithm has proved elusive. Here we report an implementation of the simplest instance of Shor's algorithm: factorization of N = 15 (whose prime factors are 3 and 5). We use seven spin-1/2 nuclei in a molecule as quantum bits, which can be manipulated with room temperature liquid-state nuclear magnetic resonance techniques. This method of using nuclei to store quantum information is in principle scalable to systems containing many quantum bits, but such scalability is not implied by the present work. The significance of our work lies in the demonstration of experimental and theoretical techniques for precise control and modelling of complex quantum computers. In particular, we present a simple, parameter-free but predictive model of decoherence effects in our system.