Causal Limit on Quantum Communication.

The capacity of a channel is known to be equivalent to the highest rate at which it can generate entanglement. Analogous to entanglement, the notion of a causality measure characterizes the temporal aspect of quantum correlations. Despite holding an equally fundamental role in physics, temporal quantum correlations have yet to find their operational significance in quantum communication. Here we uncover a connection between quantum causality and channel capacity. We show the amount of temporal correlations between two ends of the noisy quantum channel, as quantified by a causality measure, implies a general upper bound on its channel capacity. The expression of this new bound is simpler to evaluate than most previously known bounds. We demonstrate the utility of this bound by applying it to a class of shifted depolarizing channels, which results in improvement over previously known bounds for this class of channels.

Post hoc Verification of Quantum Computation.

We propose a set of protocols for verifying quantum computing at any time after the computation itself has been performed. We provide two constructions: one requires five entangled provers and a completely classical verifier; the other requires a single prover, a verifier, who is restricted to measuring qubits in the X or Z basis, and one-way quantum communication from the prover to the verifier. These results demonstrate that the verification can be achieved independently from the blindness. We also show that a constant round protocol with a single prover and a completely classical verifier is not possible, unless bounded error quantum polynomial time (BQP) is contained in the third level of the polynomial hierarchy.

Iterated Gate Teleportation and Blind Quantum Computation.

Blind quantum computation allows a user to delegate a computation to an untrusted server while keeping the computation hidden. A number of recent works have sought to establish bounds on the communication requirements necessary to implement blind computation, and a bound based on the no-programming theorem of Nielsen and Chuang has emerged as a natural limiting factor. Here we show that this constraint only holds in limited scenarios, and show how to overcome it using a novel method of iterated gate teleportations. This technique enables drastic reductions in the communication required for distributed quantum protocols, extending beyond the blind computation setting. Applied to blind quantum computation, this technique offers significant efficiency improvements, and in some scenarios offers an exponential reduction in communication requirements.

Hardness of classically simulating the one-clean-qubit model.

Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.

Optimal blind quantum computation.

Blind quantum computation allows a client with limited quantum capabilities to interact with a remote quantum computer to perform an arbitrary quantum computation, while keeping the description of that computation hidden from the remote quantum computer. While a number of protocols have been proposed in recent years, little is currently understood about the resources necessary to accomplish the task. Here, we present general techniques for upper and lower bounding the quantum communication necessary to perform blind quantum computation, and use these techniques to establish concrete bounds for common choices of the client's quantum capabilities. Our results show that the universal blind quantum computation protocol of Broadbent, Fitzsimons, and Kashefi, comes within a factor of 8/3 of optimal when the client is restricted to preparing single qubits. However, we describe a generalization of this protocol which requires exponentially less quantum communication when the client has a more sophisticated device.

Quantum walks with encrypted data.

In the setting of networked computation, data security can be a significant concern. Here we consider the problem of allowing a server to remotely manipulate client supplied data, in such a way that both the information obtained by the client about the server's operation and the information obtained by the server about the client's data are significantly limited. We present a protocol for achieving such functionality in two closely related models of restricted quantum computation-the boson sampling and quantum walk models. Because of the limited technological requirements of the boson scattering model, small scale implementations of this technique are feasible with present-day technology.

Quantum advantage for probabilistic one-time programs.

One-time programs, computer programs which self-destruct after being run only once, are a powerful building block in cryptography and would allow for new forms of secure software distribution. However, ideal one-time programs have been proved to be unachievable using either classical or quantum resources. Here we relax the definition of one-time programs to allow some probability of error in the output and show that quantum mechanics offers security advantages over purely classical resources. We introduce a scheme for encoding probabilistic one-time programs as quantum states with prescribed measurement settings, explore their security, and experimentally demonstrate various one-time programs using measurements on single-photon states. These include classical logic gates, a program to solve Yao's millionaires problem, and a one-time delegation of a digital signature. By combining quantum and classical technology, we demonstrate that quantum techniques can enhance computing capabilities even before full-scale quantum computers are available.

Universality of quantum computation with cluster states and (X, Y)-plane measurements.

Measurement-based quantum computing (MBQC) is a model of quantum computation where quantum information is coherently processed by means of projective measurements on highly entangled states. Following the introduction of MBQC, cluster states have been studied extensively both from the theoretical and experimental point of view. Indeed, the study of MBQC was catalysed by the realisation that cluster states are universal for MBQC with (X, Y)-plane and Z measurements. Here we examine the question of whether the requirement for Z measurements can be dropped while maintaining universality. We answer this question in the affirmative by showing that universality is possible in this scenario.

A quantum approach to homomorphic encryption.

Encryption schemes often derive their power from the properties of the underlying algebra on the symbols used. Inspired by group theoretic tools, we use the centralizer of a subgroup of operations to present a private-key quantum homomorphic encryption scheme that enables a broad class of quantum computation on encrypted data. The quantum data is encoded on bosons of distinct species in distinct spatial modes, and the quantum computations are manipulations of these bosons in a manner independent of their species. A particular instance of our encoding hides up to a constant fraction of the information encrypted. This fraction can be made arbitrarily close to unity with overhead scaling only polynomially in the message length. This highlights the potential of our protocol to hide a non-trivial amount of information, and is suggestive of a large class of encodings that might yield better security.

Quantum correlations which imply causation.

In ordinary, non-relativistic, quantum physics, time enters only as a parameter and not as an observable: a state of a physical system is specified at a given time and then evolved according to the prescribed dynamics. While the state can, and usually does, extend across all space, it is only defined at one instant of time. Here we ask what would happen if we defined the notion of the quantum density matrix for multiple spatial and temporal measurements. We introduce the concept of a pseudo-density matrix (PDM) which treats space and time indiscriminately. This matrix in general fails to be positive for measurement events which do not occur simultaneously, motivating us to define a measure of causality that discriminates between spatial and temporal correlations. Important properties of this measure, such as monotonicity under local operations, are proved. Two qubit NMR experiments are presented that illustrate how a temporal pseudo-density matrix approaches a genuinely allowed density matrix as the amount of decoherence is increased between two consecutive measurements.

Demonstration of blind quantum computing.

Quantum computers, besides offering substantial computational speedups, are also expected to preserve the privacy of a computation. We present an experimental demonstration of blind quantum computing in which the input, computation, and output all remain unknown to the computer. We exploit the conceptual framework of measurement-based quantum computation that enables a client to delegate a computation to a quantum server. Various blind delegated computations, including one- and two-qubit gates and the Deutsch and Grover quantum algorithms, are demonstrated. The client only needs to be able to prepare and transmit individual photonic qubits. Our demonstration is crucial for unconditionally secure quantum cloud computing and might become a key ingredient for real-life applications, especially when considering the challenges of making powerful quantum computers widely available.