Quantum computers are expected to offer substantial speedups over their classical counterparts and to solve problems that are intractable for classical computers. Beyond such practical significance, the concept of quantum computation opens up new fundamental questions, among them the issue whether or not quantum computations can be certified by entities that are inherently unable to compute the results themselves. Here we present the first experimental verification of quantum computations. We show, in theory and in experiment, how a verifier with minimal quantum resources can test a significantly more powerful quantum computer. The new verification protocol introduced in this work utilizes the framework of blind quantum computing and is independent of the experimental quantum-computation platform used. In our scheme, the verifier is only required to generate single qubits and transmit them to the quantum computer. We experimentally demonstrate this protocol using four photonic qubits and show how the verifier can test the computer's ability to perform measurement-based quantum computations. The prevalent scientific paradigm of testing physical theories by comparing experimental results with predictions computed on a piece of paper or on a computer assumes that all such predictions are solvable in polynomial time on a classical computer. In current experiments involving quantum particles, such as fundamental tests of quantum mechanics or small-scale quantum computations and simulations [1] [2] [3] [4] [5] , following this paradigm is still possible, as the results can be calculated on a classical computer and verified in experiments involving quantum systems. However, there is an entire class of problems-for example, the simulation of complex quantum systems [6] -that are solvable in polynomial time only on a quantum computer [7] . One of the central conceptual questions in current quantum computing is therefore whether any entity can test the results obtained by a quantum computer, even when that entity is unable to compute these results itself. Or, from a different perspective, can an experimentalist with only classical resources or restricted quantum resources prove that a given device is a quantum computer [8] ? Whereas the ultimate answer to such questions is still open, there are several proposals that offer a solution when the verifier is equipped with a range of quantum resources [9-14]-quantum memory, two entangled quantum computers, or a large number of qubits-which, however, are outside the reach of current technology. Here, we demonstrate how to verify a quantum computation on four qubits. Our method is directly applicable to current technology and can be readily extended to more general cases. We show that only minimal quantum resources (specifically, single qubits) are required to certify a quantum-information processor. Our protocol is independent of the physical system on which it is implemented and it can therefore be applied to any quantum- While the question of whether a classical verifier can test a quantum system is still open, it was shown that a verifier who has access to certain quantum resources can verify quantum computations. Here, in the framework of blind quantum computing, the verifier has to be able to generate single qubits and to transmit them to the prover. After the transmission of the qubits, the verifier and the prover exchange two-way classical communication. computing platform. We have implemented the new protocol on a photonic quantum system and demonstrate the necessary components for verifying a quantum device. We also show how our scheme can be used to verify the generation of the archetype of a quantum-computational resource, quantum entanglement, via a violation of Bell's inequality. In such a verification, the prover remains blind and cannot distinguish the verification procedure from standard quantum-computational tasks such as single-or multiqubit gates or entire quantum algorithms. To the best arXiv:1309.0005v1 [quant-ph] 30 Aug 2013 2 of our knowledge, this is the first experiment towards certifying the correctness of a quantum computation. Our protocol combines interactive proof systems and blind quantum computing [9] [10] [11] . Interactive proof systems were originally invented in the field of computer science, to approach questions in classical complexity theory [15, 16] . They have since been extended into the realm of quantum computation [7] . A quantum prover interactive proof system addresses the question of whether a prover who has access to quantum-computational resources can convince a classical verifier that he can solve a given problem. Interactive proof systems can therefore be used to address the fundamental questions posed above, provided the traditional scientific paradigm of "predicting" is replaced by "verifying". In our protocol, the framework of the interactive proof system is given by blind quantum computing ( Fig. 1) . In this framework, a verifier (or client) with limited quantum computational resources can delegate a quantum computation to a prover (or server) with the full power of quantum computing such that all data and the whole computation remain private [10, 17] . More specifically, the verifier prepares single qubits in the state with θ j ∈ {0, π/4, ..., 7π/4} chosen uniformly at random and only known to the verifier. The qubits are then transmitted to the prover who entangles them to create a blind cluster state [18] . The actual computation is measurement-based [19, 20] . The verifier calculates for each blind qubit measurement instructions according to where θ j is the blind phase of the qubit, φ j is the rotation that the verifier wants to perform (including any Pauli corrections), and r j ∈ {0, 1} is a randomly chosen value to hide the measurement outcome. The prover performs measurements in the basis and delivers the results to the verifier. Without the knowledge of the underlying rotation and the random phase, the prover cannot find out anything about the actual rotation φ j -thus the computation remains blind. The verifier, in contrast, knows the initial rotation and is able to interpret the results. Blind quantum computing therefore provides a powerful tool to delegate computations and to access the resources of powerful quantum computers without divulging the content of the computation. In the following, we show how this concept can be applied to verify quantum computations. In the framework of blind quantum computing, in order to test a quantum computation, the correctness of the measurements performed by the server has to be verified. Here we use a verification procedure that is based on the creation of trap qubits [12] . Trap qubits are blindly prepared in a well-defined state, which is only known to the verifier, and are isolated from the actual computation. The measurement angle of these trap qubits is chosen such that the measurement result is predetermined by the verifier, and hence any cheating strategy used by the server that alters these measurement outcomes will be detected. By randomly choosing the locations of the trap qubits it is then possible to bound the probability that the server can cheat while remaining undetected. In our setting, we implement the preparation of the trap qubits through a measurement-based computation on the non-trap qubits. The verifier chooses measurement settings on the cluster state such that any of the qubits could become a trap qubit, prepared in a random state |θ j . If the trap qubit is then measured in the basis |θ j , the outcome will always be known to the verifier (see Fig. 2 ). Our measurement-based creation of the trap qubits means that we verify a correlation between a subset of measurements, rather than a single measurement outcome. We therefore have to be careful to ensure that the correctness of these correlations for all trap measure- ments does imply the correctness of a given computational run. In our demonstration using a four-qubit system, only one error remains undetected (see Appendix). However, this particular error cannot alter the result of the measurement of Bell's quantity presented in this paper. This verification procedure can be used to verify that the quantum computation was performed correctly. Therefore, we consider multiple runs of the protocol, where the verifier randomly choses to run an actual computation or a verification test (see Fig. 3 ). This use of multiple runs of the blind-computation protocol lets us make optimal use of the qubits available in our system. Moreover, the server cannot distinguish between an actual computation run or a trap run. Hence, as discussed in details in the appendix, this procedure can be used to verify not only the correctness of the measurement outcomes but also of the entire quantum computation. When trap computation and target computation are randomly interspersed, then the probability that the quantum computer produces the correct result for the verification runs but a wrong result for the computation runs is bounded by a value depending on three parameters: the number of computation runs, the number of trap runs, and on the total number of qubits in the system (see appendix). Once the measurement outcomes are verified, we can proceed to use the system to probe the prover's entangling capabilities and its ability to create cluster states. Quantum correlations are typically confirmed by wellestablished tests of Bell's inequality [21] (Fig. 4) . In order to do so, combinations of specific measurement settings α, α and β, β are performed on the first (a) and on the second qubit (b), respectively, after generating an entangled state |Ψ a,b . The settings are chosen such that a maximal violation of the Bell inequality of the Clauser- b) The blind zigzag cluster state, and c) its corresponding circuit. If the rotation in the lower wire, −δ4 + θ4, is chosen equal to zero (or π), the input state in the lower wire will be equal to |0 b (|1 b ); otherwise, if the rotation is chosen equal to ±π/2 the input will be |±i b . The edge between qubits 2 and 3 performs a CPhase gate on the two qubits, which results in an entangled state in the former case, and in an unentangled state in the latter. The values of δ1, δ2, and δ3, as well as the phases θ1, θ2, and θ3 determine the Bell measurement settings. Horne-Shimony-Holt (CHSH) type [22] is obtained for an entangled state: The correlation coefficients E(·, ·) are defined by the coincidence counts when measuring qubit a in the basis α and qubit b in the basis β (for details see appendix). In order to make the Bell test blind, we hide the generation of the entangled state as well as the Bell measurement settings. For this, we base our implementation on a blind zigzag cluster state with four qubits |θ j , which is shown in Fig. 4b . Single-qubit measurements on the blind zigzag cluster state realize a quantum circuit that offers exactly the degrees of freedom that are necessary for our blind Bell test. First, using this type of cluster, the verifier has the possibility to blindly switch between entangled or separable input states by choosing δ 4 and θ 4 accordingly. Second, the standard measurement settings for a Bell test are hidden as they are determined by the phases of the blind qubits |θ 1 , |θ 2 , and |θ 3 and their respective measurement settings of δ 1 , δ 2 , and δ 3 (see appendix for details). As a result, the state generation as well as the Bellstate measurements are encoded in the phase of blind qubits as well as in the measurement instructions, which remain unknown to the prover at any time. The choice of the cluster-state configuration also remains hidden from the prover. This is a particular advantage of our probabilistic implementation of blind quantum computing, where all qubits are measured. We use the particular advantages offered by photons to realize a quantum network that can communicate and process quantum information [23] within the same physical system [18] . In our experiment, the blind cluster states are generated from photon pairs entangled in polarization and mode, which originate from spontaneous parametric down-conversion [24] . Our setup and the methods used are explained in detail in ref. 10; in the present experiment, we generate blind cluster states for various settings of θ j and use them to implement exemplary runs of trap computations as well as the Bell-test runs-the necessary building blocks of a verified test of Bell's quantity. For the demonstration of the measurement verification, we use blind linear cluster states and blind rotated horseshoe cluster state to prepare traps as shown in Fig. 2a  and 2b . By choosing the blind phases θ j and measurement settings δ j as given in the appendix, we prepare the traps: |trap 2 = |+ and |+ i (6) |trap 3 = R z (3π/4)|+ and R z (π/4)|+ (7) on qubits 1, 2, 3, and 4, respectively (|± = (|0 ± |1 )/ √ 2, |± i = (|0 ± i|1 )/ √ 2). The probabilities to find the correct outcome are well above 90%, as shown in Fig. 2c . For a verification of quantum entanglement, we choose combinations of θ 4 and δ 4 to create the entangled state: and to blindly implement the Bell measurements settings we choose: where the bases α, β, and β are defined as {(|0 ± e iα |1 )/ √ 2} etc., and α is a measurement in the basis {|0 , |1 }. To obtain the measurement settings given in Eq. (10), we choose combinations of |θ j and δ j as given in detail in the appendix. From the measured coincidence count rates, we calculate the correlation coefficients to be: E(α , β) = −0.646 ± 0.067 (13) Those coefficients lead to an S parameter of which violates the classical bound (|S| = 2) by more than 3 standard deviations. The combination of the verification procedure and this violation of Bell's inequality suffices to unambiguously verify the prover's ability to perform entangling gates between qubits and thus to create cluster states. In our experiment, we implement a subset of all possible blind states. The states of qubits 1 and 4 are fixed to |+ , whereas the states of qubits 2 and 3 are fully blind [18] . The whole verification procedure remains blind, however, if we assume that the prover has no a priori knowledge of our choice of states and measurements. The violation of Bell's inequalities is impossible classically, not for the reason of high complexity, but rather on the basis of physical principles. In our implementation, we assume the correctness of quantum mechanics for the verification of the measurement outcomes. Without this assumption, a full demonstration would require the two entangled photons to be sent to two distant laboratories, where only at the very last step of the computation the verifier gives the measurement instructions to the prover. In this way, no classical computer could mimic, even in principle the output of the computation a priori, while the verification procedure would still have a positive outcome. Future large-scale quantum computers and quantum simulators [25] [26] [27] [28] will require the verification of their experimental results [29] . Due to the superior computational capacity of quantum systems the results cannot simply be calculated and checked on a classical device. The development of new methods for the verification of quantum computations is therefore a crucial task. Here, we have developed a new general method for verifying quantum computations that can be readily applied to current small-scale quantum computers. We have shown, in theory and in experiment, how a verifier can test whether the quantum computer is quantum and even whether it computes correctly. Finally, how verification mechanisms provide insights into questions of computational complexity and into the foundations of quantum physics it is a topic of active current research. To date, the limit of high computational complexity is mostly unexplored and it is not impossible that quantum mechanics breaks down at some scale of complexity [30] . Verification methods, such as those reported here in are not only important as a mechanism to certify quantum computers, but also provides an entirely novel toolbox for addressing fundamental questions in quantum physics and computer science. [1] D. Deutsch, Proc. R. Soc. A 400, 97 (1985). [2] D.
A small-scale version of this protocol was implemented in quantum optics REF .
Experimental verification of quantum computations
Nature Physics 9, 727-731 (2013)
Physics