Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements.

Measurement-based quantum computing is one of the most promising quantum computing models. Although various universal resource states have been proposed so far, it was open whether only two Pauli bases are enough for both of universal measurement-based quantum computing and its verification. In this paper, we construct a universal hypergraph state that only requires X and Z-basis measurements for universal measurement-based quantum computing. We also show that universal measurement-based quantum computing on our hypergraph state can be verified in polynomial time using only X and Z-basis measurements. Furthermore, in order to demonstrate an advantage of our hypergraph state, we construct a verifiable blind quantum computing protocol that requires only X and Z-basis measurements for the client.

Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error.

The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)PRLTAO0031-900710.1103/PhysRevLett.112.130502]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)PRLAAZ1364-502110.1098/rspa.2010.0301] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.

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.

Erratum: Detection of Macroscopic Entanglement by Correlation of Local Observables [Phys. Rev. Lett. 95, 090401 (2005)].

This corrects the article DOI: 10.1103/PhysRevLett.95.090401.

Verifiable Measurement-Only Blind Quantum Computing with Stabilizer Testing.

We introduce a simple protocol for verifiable measurement-only blind quantum computing. Alice, a client, can perform only single-qubit measurements, whereas Bob, a server, can generate and store entangled many-qubit states. Bob generates copies of a graph state, which is a universal resource state for measurement-based quantum computing, and sends Alice each qubit of them one by one. Alice adaptively measures each qubit according to her program. If Bob is honest, he generates the correct graph state, and, therefore, Alice can obtain the correct computation result. Regarding the security, whatever Bob does, Bob cannot get any information about Alice's computation because of the no-signaling principle. Furthermore, malicious Bob does not necessarily send the copies of the correct graph state, but Alice can check the correctness of Bob's state by directly verifying the stabilizers of some copies.

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.

Secure entanglement distillation for double-server blind quantum computation.

Blind quantum computation is a new secure quantum computing protocol where a client, who does not have enough quantum technologies at her disposal, can delegate her quantum computation to a server, who has a fully fledged quantum computer, in such a way that the server cannot learn anything about the client's input, output, and program. If the client interacts with only a single server, the client has to have some minimum quantum power, such as the ability of emitting randomly rotated single-qubit states or the ability of measuring states. If the client interacts with two servers who share Bell pairs but cannot communicate with each other, the client can be completely classical. For such a double-server scheme, two servers have to share clean Bell pairs, and therefore the entanglement distillation is necessary in a realistic noisy environment. In this Letter, we show that it is possible to perform entanglement distillation in the double-server scheme without degrading the security of blind quantum computing.

Efficient universal blind quantum computation.

We give a cheat sensitive protocol for blind universal quantum computation that is efficient in terms of computational and communication resources: it allows one party to perform an arbitrary computation on a second party's quantum computer without revealing either which computation is performed, or its input and output. The first party's computational capabilities can be extremely limited: she must only be able to create and measure single-qubit superposition states. The second party is not required to use measurement-based quantum computation. The protocol requires the (optimal) exchange of O(Jlog2(N)) single-qubit states, where J is the computational depth and N is the number of qubits needed for the computation.

Blind topological measurement-based quantum computation.

Blind quantum computation is a novel secure quantum-computing protocol that enables Alice, who does not have sufficient quantum technology at her disposal, to delegate her quantum computation to Bob, who has a fully fledged quantum computer, in such a way that Bob cannot learn anything about Alice's input, output and algorithm. A recent proof-of-principle experiment demonstrating blind quantum computation in an optical system has raised new challenges regarding the scalability of blind quantum computation in realistic noisy conditions. Here we show that fault-tolerant blind quantum computation is possible in a topologically protected manner using the Raussendorf-Harrington-Goyal scheme. The error threshold of our scheme is 4.3 × 10(-3), which is comparable to that (7.5 × 10(-3)) of non-blind topological quantum computation. As the error per gate of the order 10(-3) was already achieved in some experimental systems, our result implies that secure cloud quantum computation is within reach.

Not all physical errors can be linear CPTP maps in a correlation space.

In the framework of quantum computational tensor network, which is a general framework of measurement-based quantum computation, the resource many-body state is represented in a tensor-network form (or a matrix-product form), and universal quantum computation is performed in a virtual linear space, which is called a correlation space, where tensors live. Since any unitary operation, state preparation, and the projection measurement in the computational basis can be simulated in a correlation space, it is natural to expect that fault-tolerant quantum circuits can also be simulated in a correlation space. However, we point out that not all physical errors on physical qudits appear as linear completely-positive trace-preserving errors in a correlation space. Since the theories of fault-tolerant quantum circuits known so far assume such noises, this means that the simulation of fault-tolerant quantum circuits in a correlation space is not so straightforward for general resource states.

Continuous-variable blind quantum computation.

Blind quantum computation is a secure delegated quantum computing protocol where Alice, who does not have sufficient quantum technology at her disposal, delegates her computation to Bob, who has a fully fledged quantum computer, in such a way that Bob cannot learn anything about Alice's input, output, and algorithm. Protocols of blind quantum computation have been proposed for several qudit measurement-based computation models, such as the graph state model, the Affleck-Kennedy-Lieb-Tasaki model, and the Raussendorf-Harrington-Goyal topological model. Here, we consider blind quantum computation for the continuous-variable measurement-based model. We show that blind quantum computation is possible for the infinite squeezing case. We also show that the finite squeezing causes no additional problem in the blind setup apart from the one inherent to the continuous-variable measurement-based quantum computation.

Detection of macroscopic entanglement by correlation of local observables.

We propose a correlation of local observables on many sites in macroscopic quantum systems. By measuring the correlation one can detect, if any, superposition of macroscopically distinct states, which we call macroscopic entanglement, in arbitrary quantum states that are (effectively) homogeneous. Using this property, we also propose an index of macroscopic entanglement.