Quantum computers have attracted tremendous interest because they promise to outperform classical computers at a number of tasks¹. The long-term goal is to build a universal quantum processor, which can be programmed to solve arbitrary problems². Doing so will require decomposing quantum computations into sequences of quantum gates acting on only a few qubits¹. In particular, any computation can be decomposed using single-qubit gates and a particular two-qubit entangling gate such as controlled-NOT (CNOT). In linear-optical quantum computing, two-qubit gates are difficult to implement because photons do not interact directly, meaning that the difficulty of a computation can be described by the number of entangling gates it requires.

Entangling gates can be implemented optically by introducing an effective nonlinearity via measurements³, but this implies, in the simplest case, that output photons of a two-qubit gate need to be measured to ensure correct gate operation, making another application of gates to the same pair of qubits impossible^{4,5,6,7,8,9,10,11}. Here, we demonstrate two CNOT gates acting on the same pair of qubits. We implement the two CNOTs differently: the success of the first gate is heralded by the successful detection of two ancillary photons^12,13, while the second gate is probabilistic^5,6,7. In distinction to previous work¹¹, our scheme does not involve qubit recycling which, in principle, can be performed deterministically.

We then use our setup to determine the solution of several two-dimensional systems of linear equations. Whereas for a classical computer the number of computational steps needed to solve a linear system is at least proportional to the number of variables, a recently developed quantum algorithm could, in some circumstances, make the computational time proportional to only the logarithm of the number of variables¹⁴. An important difference is that the quantum algorithm calculates the expectation value of an operator associated with the solution rather than the solution itself. We note that this algorithm has been implemented previously in photonic systems¹⁵ and also using NMR techniques^16,17. We use the algorithm as an example of the correct operation of two consecutive CNOTs, a flexible approach that differs from previous implementations. As we note below, our method is as powerful as that in¹⁵. Our implementation thus presents a general quantum circuit with two consecutive CNOT gates which can be flexibly adapted to solve other problems. This is a step towards a two-qubit universal quantum processor, which would require three consecutive CNOT gates.

In our experiment, we use polarisation-encoded photonic qubits (Fig. 1,Fig. 2 and3b), where |0〉 and |1〉 denote horizontal and vertical polarisation, respectively^18,19. We produce entangled photon pairs using non-collinear type-II spontaneous parametric down-conversion (SPDC)²⁰. A pulsed UV laser beam (394.5 nm, 76 MHz, τ = 200 fs) passes through a 2 mm-thick β-barium borate crystal, gets reflected and passes through the crystal a second time (seeFig. 1).

Experimental setup.

Shown is the experimental implementation of two concatenated CNOT gates. The input is set by a polariser, which can be followed by a local unitary operation (LU). The two gates are connected by fibers. Different matricesA can be implemented by adapting the LUs and different states |b〉 by adapting the input state. The figure shows the most general case of two concatenated CNOT gates, combined with general LUs. For the implementation of the algorithm, we chose some LUs to be the identity and obtained the case shown inFig. 3a.

Full size image

Example of a result of a computation on our two-qubit quantum processor.

(a) The input to the circuit is chosen to be the state |1〉|0〉. Then we apply a CNOT gate, followed by a Hadamard gate on the control qubit. Finally, we implement the second CNOT gate and characterise the output state via two-qubit state tomography. (b) the ideal output state and (c) the reconstructed density matrix (real parts), which has a fidelity of 0.717 ± 0.030 with the ideal state. The imaginary part is below 0.1 and hence not shown.

Full size image

(a) Simplified circuit for the algorithm for solving specific systems of linear equations. Given a Hermitian matrixA and input |b〉, outputs |x〉 =A⁻¹ |b〉/||A⁻¹ |b〉|| if the ancilla qubit is measured to be 1. The local unitaryR diagonalisesA, and θ = −2 arccos(λ₁/λ₂), where λ_1,2 are the eigenvalues ofA. (b) Experimental implementation of the circuit in a. The local unitary operations are implemented with the help of a combination of half-wave plates and quarter-wave plates. (c) The figure shows a system of linear equations, described by the matrixA₁ as well as the state vector |b₁〉. (d) The reconstructed density matrix of the experimentally obtained output state |x〉 is shown. This density matrix is obtained by choosing the local operation. We choose the eigenvalues to be and by implementingR_y(θ) correspondingly. The fidelity of the reconstructed density matrix is 0.953 ± 0.026. The wire frame shows the theoretical prediction. (e) The quantum algorithm is based on determining the expectation value 〈x|M|x〉 of some operatorM with respect to the output state |x〉. Therefore, we also show the experimentally determined (blue) and theoretical (black) expectation values of several operatorsM. We choose the operatorM to be the projection on the states |0〉, |+〉 and |+_i〉, respectively, with and. Another example is shown in theSI (Fig. S3).

Full size image

The photons created during the first pass of the laser beam enter the first CNOT as the input (control and target) qubits. The state of these input qubits can be modified using additional local gates and polarisers, which in principle allows for the creation of arbitrary input states. The first CNOT uses an entangled ancillary photon pair and a successful measurement of two ancilla modes heralds that the gate has worked correctly on the input qubits^12,13. The photons created during the second pass act as the entangled ancillary photon pairs, in the state. The photons interfere at the polarising beam splitters (PBS) as shown inFig. 1. The PBS on the control (target) side is aligned to act in the basis. The photons are filtered spectrally and spatially using narrow-band filters (Δλ = 3 nm) and by coupling them into single-mode fibers. A coincidence detection of the ancilla qubits in detectors 3 and 4 in the state |–〉₃|1〉₄ signals a successful gate operation^5,6,7.

The output photons of the first CNOT (modes I and II inFig. 1) are then guided to the second CNOT. This gate is implemented in a destructive way, where a coincident measurement of the output photons signals the correct gate operation. The basic element of this destructive CNOT is a polarisation-dependent beam splitter (PDBS) which has a different transmission coefficientT for horizontally and vertically polarised light (T_H = 1,T_V = 1/3)^5,6,7. If two vertically-polarised photons are reflected at this PDBS, they acquire a phase shift of π. Subsequent PDBSs with opposite splitting ratios equalise the output amplitudes. This setup, in combination with two half-wave plates (HWPs) (Fig. 3b) implements a destructive CNOT. The success of this second CNOT is determined by postselection on a coincidence detection in outputs 1 and 2.

Combining these photonic CNOT gates with local unitary operations allows us to implement a two-qubit quantum processor. In our setup, we implement these local unitary operations using quarter- and half-wave plates (QWP and HWP), which can be easily adjusted to program the quantum computer (Fig. 1 and3b).Fig. 2 shows a sample run of our experiment; details about experimental parameters can be found in Methods and in theSupplementary Information (SI).

We use our two-qubit quantum processor to solve systems of linear equations, which, given a matrixA and a vectorb, means finding the vectorx such thatAx =b. If we rescale the vectors to ||b|| = ||x|| = 1 and represent them as quantum states |b〉 and |x〉, the task becomes finding |x〉 such that

The solution is |x〉 =A⁻¹ |b〉/||A⁻¹ |b〉||.

The quantum algorithm¹⁴ consists of three steps, described in Methods. There, we also discuss the simplest possible realisation of the algorithm, for a 2 × 2 matrixA and its reduction to the simplified circuit shown inFig. 3a. This circuit depends on the eigenvalues, λ₁ and λ₂, of the matrixA, the unitaryR that diagonalises it,

and the input state |b〉.

We have implemented various instances of the algorithm, varying all the parameters inA,R and |b〉. The control and target qubits are prepared in the statesR|b〉 and |1〉, respectively, absorbing the local operationR into the preparation of the input state. The matrixA can be modified by tuning the local operationR (in which case the eigenvalues stay the same) or by adapting the eigenvalues of the matrix, λ₁ and λ₂, which is done by adapting the local unitary operations before and after the second CNOT gate (seeFig. 3). Finally, the detection of the ancilla qubit in the state |1〉 announces a successful run of the algorithm and the preparation of the output qubit in the state |x〉. The success probability is (λ₁/λ₂)². Because we are able to distinguish two eigenvalues, our method, although different and using logical fewer qubits, is as powerful as that of Caiet al¹⁵.

The output state is analysed using HWPs, QWPs and polarising beam splitters and a full state tomography is performed. Error estimates are obtained from a Monte Carlo routine assuming Poissonian counting statistics. These indicate a lower bound for the actual error that takes all the experimental imperfections into account.

Detailed results of a sample run of the algorithm are shown inFig. 3. Additional results are presented inFig. 4, where the input states and the eigenvalues ofA are varied. It can be seen there that the performance of the algorithm depends on the input stateR|b〉. To analyse this behaviour, we chose two different input states, |b₁〉 = |1〉 and |b₂〉 = |+〉 for eachA, while keepingR equal to the identity matrix. We achieve fidelities of up to 0.981 ± 0.009 for |b₁〉 and 0.832 ± 0.031 for |b₂〉. The difference in fidelities arises due to the influence of higher-order emissions, as discussed in theSI. Data for additional choices ofA,R and |b〉 are shown in theSI. The reported density matrices contain the raw measured data and have not been modified in the post processing.

The figure shows the solution of the system of linear equation for matrices with different eigenvalues.

Experimentally, these are obtained by implementing different values of θ. For all matrices we run the algorithm for two input states |b₁〉 = |1〉 = (0,1) and. We achieve fidelities of 0.957 ± 0.010, 0.961 ± 0.013, 0.981 ± 0.009 for the input state |b₁〉 (upper row from left to right) and 0.778 ± 0.031, 0.773 ± 0.027, 0.832 ± 0.031 for the input state |b₂〉 (lower row, left to right).

Full size image

We present a two-qubit quantum circuit with two concatenated entangling gates acting on the same pair of photonic qubits and employ our system to implement the simplest case of the quantum algorithm for solving systems of linear equations. With demonstrating the consecutive application of two CNOT gates on the same pair of qubits, we have addressed a technological challenge in photonic quantum computation. This development is a step towards universal multi-qubit quantum processors using single photons as a versatile platform for computation and simulation.

We anticipate that increasing technological capabilities, including the implementation of more than two consecutive CNOTs, will allow the extension of the algorithm both to larger systems and to more precise phase estimation. Eventually, this will allow not only solving larger systems of linear equations, but also equally important algorithms that use it as a subroutine, including quantum algorithms for solving nonlinear differential equations²¹ and quantum data fitting²².

Theory

We assume, without loss of generality¹⁴, thatA is anN ×N Hermitian matrix with eigenbasis {|u_j〉} and eigenvalues {λ_j}, rescaled so that 0 < λ_j < 1. If |b〉 is expanded as, we aim to prepare, up to normalization,

The quantum algorithm¹⁴ consists of three steps. The most general circuit involves phase estimation, a controlledR_y rotation and a reverse phase estimation. Our work differs from the original proposal¹⁴ in several modifications that are needed to implement the algorithm with a limited number of qubits. Here, we briefly outline the algorithm while noting our modifications.

The first step, phase estimation, is a general procedure for decomposing quantum states into a particular basis^1,23. It requires an additional “eigenvalue” register ofm qubits, each initialised to |0〉. Phase estimation transforms into, where the eigenvalues |λ_j〉 are stored in the eigenvalue register to a precision ofm bits (binary digits).

We restrict ourselves to the simplest case, which involves one state qubit and one eigenvalue qubit. The single state qubit implies that |b〉 is a two-vector andA a 2 × 2 matrix, while the single eigenvalue qubit means that only a single bit of the eigenvalues is computed by the phase estimation. This means that for the algorithm to work perfectly, it must be possible to distinguish the two eigenvalues with reference to a single bit. Consequently, we choose the two eigenvalues to be of the form and, where is a sequence of bits. The position of the differing bit is what governs the choice of the phase estimation unitaryU. In particular, if we wish to read out thenth bit, we must chooseU = exp (2πi 2ⁿ⁻¹A). We note that choosing eigenvalues that could not be distinguished using a single bit would lead to additional rounding errors, which would, in principle, be avoidable with a larger quantum computer.

The two-qubit phase estimation transforms the state and eigenvalue qubits, initialised to |b〉_S|0〉_E to, where is thenth bit of λ_j. Each eigenstate in the state register is now entangled to thenth bit of its eigenvalue.

The second step is the nonunitary map. For this, we introduce an additional “ancilla” qubit initialised to |1〉 and controlled on the value in the eigenvalue register, we implement a controlled-R_y(θ_j) = exp(−iθ_jσ_y/2) rotation on the ancilla qubit, where σ_y is the Pauli matrix. With (whereC ≤ min_j |λ_j|), the overall state becomes

The third step is to run phase estimation in reverse to uncompute, giving

We measure the ancilla and if we observe a 1 we will have prepared |x〉 in the state register. If we know the eigenvalues, we can maximise the success probability by choosing the largest possibleC,C = min_j |λ_j|.

The procedure described above involves three qubits, one each for the state, eigenvalue and ancilla registers. The corresponding circuit is shown inFig. 5, which also describes how it can be simplified to the final circuit shown inFig. 3a.

The simplest case of the quantum algorithm for solving systems of linear equations.

(a) The complete circuit, as described in Methods, withU = exp (2πi 2ⁿ⁻¹A) and θ = −2 arccos(λ₁/λ₂), where λ_1,2 are the eigenvalues ofA and the integern depends on the eigenvalues. (b) For the algorithm to work perfectly with one eigenvalue qubit, λ_1,2 must be distinguishable by reference to a single binary digit. In that case,, a simplification reflected in this circuit. The middle qubit can now be completely removed. Although controlled single-qubit rotations have been implemented in linear optics^24,25,26, we follow a different approach, decomposing the controlled rotation to give the final circuit shown inFig. 3a.

Full size image

Experiment

For the creation of entangled photon pairs, a mode-locked Coherent Mira HP Ti:Sa oscillator is pumped by a Coherent Inc. Verdi V-10 laser. The pulsed-laser output (τ = 200 fs, λ = 789 nm, 76 MHz) is frequency-doubled using a 2 mm-thick lithium triborate (LBO) crystal, resulting in UV pulses of 0.75 W cw average. We achieve a stable source of UV pulses by translating the LBO to avoid optical damage to the anti-reflection coating of the crystal. Our detectors have quantum efficiencies of 0.4 and dark count rates between 500 and 3500 counts per second. In our experiment, typical visibilities (fidelities) of the emitted Bell pairs of about 0.9 (0.8) and higher-order emissions degrade the quality of our gate operations. The back-reflecting mirror is continuously moved back-and-forth to avoid any phase correlations between of the signal and the noise originating from higher-order photon emissions. Additionally, imperfect visibilities on the order of 0.85 to 0.9 of the quantum interference (caused by partial distinguishability of the photons) at the PBSs in the first gate and the PDBS in the second gate contribute to errors. The measured production rate of two-fold coincidences is 18000 s⁻¹ in the forward direction and 10000 s⁻¹ in the backward direction (measured after the first gate). The total fourfold-coincidence rate is 1700 h⁻¹ (55 h⁻¹) after the first gate (both gates).

• 12 May 2017

  A correction has been published and is appended to both the HTML and PDF versions of this paper. The error has been fixed in the paper.

• 30 June 2015

  The HTML version of this Article previously published incorrectly listed Philip Walther and not Stefanie Barz, as corresponding author. This has now been corrected in the HTML; the PDF version of the paper was correct from the time of publication.

We thank Frank Verstraete for valuable discussions and Thomas Lindner for assistance in the laboratory. I.K. was supported by a UQ Postdoctoral Research Fellowship and the ARC Centres of Excellence for Engineered Quantum Systems (CE110001013) and Quantum Computation and Communication Technology (CE110001027). A.A.G. thanks the Hughes Research Laboratory (M1144-201167-DS), Air Force Research Office (FA9550-12-1-0046 and 10323836-SUB) and the Corning, Sloan and Dreyfus foundations for their support. P.W. acknowledges support from the European Commission, Q-ESSENCE (No. 248095), QUILMI (No. 295293), EQUAM (No. 323714), PICQUE (No. 608062), GRASP (No. 613024) and the ERA-Net CHISTERA project QUASAR, the John Templeton Foundation, the Vienna Center for Quantum Science and Technology (VCQ), the Austrian Nano-initiative NAP Platon, the Austrian Science Fund (FWF) through the SFB FoQuS (F4006-N16), START (Y585-N20) and the doctoral programme CoQuS, the Vienna Science and Technology Fund (WWTF, grant ICT12-041) and the United States Air Force Office of Scientific Research (FA8655-11-1-3004).

1. Stefanie Barz

   Present address: Clarendon Laboratory, Department of Physics, University of Oxford, Parks Road, OX1 3PU, Oxford, UK

2. Martin Ringbauer

   Present address: Centre for Engineered Quantum Systems and Centre for Quantum Computing and Communication Technology, School of Mathematics and Physics, The University of Queensland, Brisbane, QLD 4072, Australia

Authors and Affiliations

1. Faculty of Physics, University of Vienna, Boltzmanngasse 5, 1090, Vienna, Austria

   Stefanie Barz, Martin Ringbauer, Yannick Ole Lipp, Borivoje Dakić & Philip Walther

2. Department of Chemistry and Chemical Biology, Harvard University, Cambridge, MA, 02138, United States of America

   Ivan Kassal & Alán Aspuru-Guzik

3. Centre for Engineered Quantum Systems and Centre for Quantum Computing and Communication Technology, School of Mathematics and Physics, The University of Queensland, Brisbane, QLD 4072, Australia

   Ivan Kassal

Contributions

S.B., M.R. and Y.O.L. designed and implemented the experiment. S.B. and M.R. collected and analysed the data. I.K. and A.A.G. provided the theoretical proposal and I.K. and B.D. provided the theoretical analysis. A.A.G. and P.W. supervised the project. All authors wrote and edited the paper.

Competing interests

The authors declare no competing financial interests.

This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visithttp://creativecommons.org/licenses/by/4.0/

Reprints and permissions