In situ upgrade of quantum simulators to universal computers Benjamin Dive,1 Alexander Pitchford,2 Florian Mintert,1 and Daniel Burgarth2 1Department of Physics, Imperial College, SW7 2AZ London, UK 2Institute of Mathematics, Physics and Computer Science, Aberystwyth University, SY23 3FL Aberystwyth, UK (Dated: January 9, 2017) The ability to perform a universal set of logic gates on a quantum simulator would come close to upgrade it into a universal quantum computer [1, 2]. Knowing how to do this is very hard as it requires a precise knowledge of the simulator. In most cases, it also needs to be itself simulated on a classical computer as part of an optimal control algorithm [3, 4]. This generally can not be done efficiently for the very reason that quantum computers provide an advantage over classical ones. Here we use a simulator to discover how to implement a universal set of gates on itself without knowing the details of its own workings. The method is scalable for a series of examples and is a 7 practical way of upgrading quantum simulators to computers, as well as opening up new possible 1 architectures. 0 2 Recent and ongoing work on building large quantum n systems is leading to simulators that are able to model a J physicalphenomena,allowingquestionsabouttheunder- 6 lyingsciencetobeanswered[2,5,6]. Thesemachinesare a register of quantum particles each storing a quantum ] bit (qubit) of information in two internal states. The h presence of interactions between these leads to dynamics p - that,byvaryingcontrolparametersinthesystemHamil- t tonian, can replicate the quantum behaviour of systems n a ofinterest. This,however,islessgeneralthanaquantum u computer which is able is to perform a universal set of q logic gates on the qubits [1]. [ Provided some control parameters can be varied in 1 time,itisinprinciplepossibletodoanarbitrarygateon v aquantummany-bodysystemsuchasaquantumsimula- 3 tor[7,8]. Findingtherighttime-dependencyhoweverre- 2 lies almost exclusively on numerical methods, especially 7 when physical constraints on the control fields are taken 1 FIG. 1. A classical computer finds a control pulse which en- 0 into account [3, 4]. These require a very precise knowl- ables a quantum simulator to perform logic gates. It does . edgeoftheparametersofasystem,adauntingtaskfora 1 thisinaniterativeprocessbyapplyingacontrolpulsetothe machine with ahuge number ofdegreesof freedom. Fur- 0 simulator and then improving it based on the result of mea- thermore, they are intractable on a classical computer if 7 surements. 1 the simulator we want to solve the problem for is large : enough to do something new. v i We circumvent these problems by showing how well- the submission of this paper, a similar approach as ours X known existing numerical methods can be translated to was developed and tested experimentally for quantum r runinsitu onthequantumsimulatoritself,asillustrated state preparation [14]. a in Fig. (1). This is a scalable, bootstrapping scheme for The model we consider is a quantum simulator con- performing a universal quantum computation, needing sisting of n qubits with some interactions between them classical computational and experimental resources that suchthattheyareconnectedonatimescalemuchshorter grow only polynomially with the number of qubits. An thanthedecoherencetime,andwiththeabilitytodofast adaptiveapproachtofindingcontrolsisnaturallyusedin single qubit operations. These requirements are signifi- laboratoryworkandhasbeenstudiedasbothfine-tuning cant,butmucheasierthandemandingdirectcontrolover tool in small systems [9, 10] and a way of correcting pa- twoqubitoperations,andcorrespondtothestate-of-the- rameter drift [11]. Using simulators as oracles for reach- artinsystemsinvolvingtrappedions[16–18],coldatoms ing quantum states was explored in [12], and the poten- [19, 20] or NMR [21–23]. In these systems there already tialforaquantumspeedupingeneraloptimisationprob- exist quantum simulators powerful enough to do simula- lems in [13]. We show that this general approach can be tions,andsatisfyourrequirements,butarenotcurrently transformed into a large scale, constructive method that usable as computers as it is not known how to perform changes the way we approach the control of many-body logic gates on them [1, 2]. In the model we consider, quantum systems. Independently, and concurrently to theconnectednessofthequbitsandtheabilitytodofast 2 101 sFretIadPGraCrItsaon.minitt2ntieeraot.lgep lr sOs puiontinlittnheeisomfatiPndrhodpeianlgpeaitrte aoiarcPleeaCUrssaodpsmnedotaterutotneels r oese fdinciEoEnFffivisndacoiileteutlpnirautttyolety i limnpaaolrucaromnsetctrheoerlm,sRTe,taaehrcg.wheeetd hT tiwhchoe 1-Fidelity 1111100000----43210●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●●■●■●■●■●■●●■■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■LE●■●■●■●■●■●■●■●■●■●■■●●■●■●■●■ox●■●■●■●■●■●■●■●■●■●■●■●■ca●■●■●■●■●■●■●■●■●■●■●■ac●■●■●■●■●■●■●■●■●■●■●■lt●■●■●■●■●■●■●■●■●■●■●■●■●■●■EF●■●■●■●■●■●■●■●■●■●■●■●■●■i●■●■s●■●■●■●■●■d●■●■●■●■t●■●■●■●■●■●■●■i●■e●■●■●■●■●■●■m●■●■●■●■●■l●■●■●■●■●■●■●■i●■●■■●●■●■●■●■at●■●■●■●■●■●■●■y●■●■●■●■t●■●■●■●■●■●■o●■●■●■●■●■●■●■●■●■●■●■●■●■r●■●■●■●■●■●■●■●■●■●■●■●■●■●■o●■●■●■●■●■●■●■●■●■●■●■●■f●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■F●■●■●■●■●■●■●■●■●■●■●■●■●■●■i●■●■■●●■●■●■d●■●■●■●■●■●■●■●■●■●■●■●■●■e●■■●●■■●●■●■●■●■●■●■●■l●■●■●■●■●■●■i●■●■●■●■●■●■●■t●■●■●■●■●■●■●■y●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●●■●■●■■●●■●■■●●■■●■●●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■●■■●■●●■●■●■■● we generated randomly for our examples. The evolution of 0 100 200 300 400 500 600 the system with these parameters is then calculated. On a IterationStep classical computer this requires solving the time-dependent Schr¨odinger equation numerically for a model of the system, FIG. 3. The gate fidelity, and its local estimator Eq. 1, are while in our scheme this is simply implementing the controls plotted as a function of iteration step for one complete run on the simulator. Evaluating the gate fidelity in the classical of the in situ optimisation scheme. The system is a five- case is straightforward, but in our scheme it requires some qubit Ising chain where the target is a C-NOT gate on the form of tomography to measure it. We derived good bound first two qubits and identity on the others. The algorithm on this gate fidelity, Eq. (1), that can be found efficiently. If minimised the infidelity of the local estimator. The exact in- this fidelity is above a threshold, the process terminates suc- fidelity is plotted at each step for comparison. It is lower cessfully,otherwisethecontrolparametersareupdatedbased in every case, and highly correlated with the estimated in- on the existing and previous runs, and the process repeats. fidelity, such that minimising the former also minimises the There are many ways to update the controls classically [15] latter almost monotonically and the landscape remains trap that can also be used in this method. In our examples we free. Furthermore the difference between the two decreases usedasteepestascentmethodwhichrequiresthegradientof rapidlyastheinfidelityapproaches0. Thisdemonstratesthe thefidelityinthecontrolparameterstoalsobemeasured;we validity of maximising the local estimator of the fidelity as a show that this can also be done efficiently. proxy for maximising the true gate fidelity. single qubit operations guarantees that the two require- stead. Theexceptiontothisisthefidelity,wherewehave ments of the optimisation scheme are satisfied: there ex- a good bound that can be measured efficiently. For the ists a universal gate set that can be reached at short rangeofexamplesweconsidered,wefoundthatthetotal times [24], and process tomography can be performed cost, N , scales polynomially as O(n4). tot [25]. While other systems satisfy these requirements and Measuring the gate fidelity between the (potentially the approach detailed here would work, we focus on this noisy) realised dynamics and the target unitary is an modelforclarity. Assinglequbitoperationsareassumed, important part of the protocol. The standard method thegatesthatcontrolsareneededforareentanglingones, of doing this is to perform a variant of process tomog- canonically the controlled-not (C-NOT) gate, which are raphy, known as certification, which requires a num- vastly harder to perform using conventional methods. ber of measurements that scales exponentially:N = meas The steps for finding such a gate in the in situ scheme O(d2) = O(22n) [27]. However for cases of interest are outlined in Fig. (2). These are the same as in clas- where the target gate has a tensor product structure, sical optimal control except that the control parameters U = (cid:78)U = C-NOT ⊗1 ⊗1 ⊗..., it is possible to i 1 2 3 to be optimised are implemented on the quantum ma- get around this. The fidelity over the whole system is chine itself, rather than simulated on a classical com- bounded by the fidelities of the tensor subsystems ac- puter. This eliminates the need to characterise and sim- cording to ulatethesystem,therebyremovingthekeyelementsthat (cid:88) prevent classical optimal control theory from being effi- F(M,U)≥F (M,U)=1− (1−F(M ,U )) (1) LE i i cient. The computational cost for the in situ scheme is i the number of runs of simulator needed to find a con- trol pulse, given by N = N N N N where: whereF(M,U)isthegatefidelity[28]betweentheevolu- tot iters fids reps meas N is the number of iterations where the scheme goes tionM andtargetunitaryU,thesumisoverallelements arioteurnsd the loop of Fig. (2), Nfids the number of fideli- of the tensor product, and Mi(ρi)=M(ρi(cid:78)j(cid:54)=i d1j1j) is tiesthatmustbemeasuredperiteration,N thenum- the reduced dynamical map acting on any state in sub- reps ber of repeats of each fidelity measurement required to systemiandthemaximallymixedstateeverywhereelse, get the desired accuracy, and N is the number of which is proved in the appendix following methods from meas measurements per fidelity. Most of these depend on the [29]. By using this local estimator of the fidelity F as LE underlyingalgorithmusedand,asisusualincontrolthe- the figure of merit to optimise over, the true fidelity is ory, we do not have analytic expressions for them, so we guaranteed to be at least as high and, as we can see in present numerical evidence of how they scale with n in- Fig. (3),convergeswell. Importantly,itcanbemeasured 3 80 70 10-2 ns mberofiteratio 34560000 ffffiiiidddd====99999997..%%97%% delityaccuracy 1100--34 u fid=90% Fi N 20 10-5 10 3 4 5 6 7 3 4 5 6 7 a) Numberofqubits b) Numberofqubits FIG.4. Numerical simulation of the experimental cost of finding a C-NOT gate in an Ising chain using steepest ascent in situ. The number of iterations and the accuracy required for the optimisation protocol to succeed is plotted for a chainofqubitswithnearestneighbourinteractionsσ ⊗σ evolvingforatimeπ (forunitsof(cid:126)=1)withσ andσ controlsat z z x y eachsite. Infigurea)thefidelityaccuracyispickedtogivea50%successrateandthenumberofiterationsplottedforchains of various length and for different target fidelities (as these are F , the true gate fidelity will be somewhat better). We see LE a strong linear relation in the number of iterations required as a function of the number of qubits giving N = O(n). The iters required precision to achieve 50% success rate irrespective of the number of iterations is shown in b) for the same system, and matchesverywellwithatheoreticalfitofO(1/n). Thisfitarisesbynotingthattoreachagateinfidelityof(cid:15)oughttorequire measuringthefidelitytoanaccuracyO((cid:15));asthisiscalculatedfromthesumofthefidelitiesofthesubsystem,itisreasonable that these need to be measured to an accuracy O((cid:15)/n). This argument is backed up by how well the data lies on the curves. Fromthisdata,wecanestimateN andN . TherequiredaccuracyscalesasO(1/n)which,withthecentrallimittheorems, reps fids implies that the number of measurement repetitions N scales as O(n2). The number of fidelity measurements per iteration reps ofthecontrolparameters,N ,scalesasO(n). Thisisbecauseasteepestascentalgorithmrequiresthegradientofthefidelity fids for each of the control parameters in order to update them. The most direct way of obtaining these gradients is to repeat the simulationwitheachofthecontrolparametersincreasedbyasmallfiniteamountinturnandcalculatetheapproximatefinite differencegradient(thiswasnotdoneinournumericalsimulationsasitwastoolargeacomputationalcost,ananalyticgradient obtained using GRAPE [26] was used instead). This requires one additional fidelity to be measured per control parameter. In our algorithm (and GRAPE), each of the control Hamiltonians is divided into a number of time slots of constant amplitude. Surprisingly, we found that the required number of time slots for the protocol to work on the Ising chain was 12, independent of the length of the chain. As there are 2 control parameters per qubit (corresponding to σ and σ ) per time slot, this gives x y N =O(n). fids efficiently due to the need to perform certification over machine. We also surveyed a range of different possible small subspaces only, as scaling the scheme up increases simulatortopologiesandinteractiontype,assummarised the number of subspaces but not their size. This leads in Fig. (5). In all cases the scheme worked at reasonable to, N =O(1), an exponential decrease in the cost of cost, with the Ising chain and star working particularly meas estimating the gate fidelity. well. Alastpointtoinvestigateisthattheschememight failandnotconvergetothedesiredgate. Asweareusing The scaling relation of the other components of N a gradient based method, this would happen if there is a tot depends on the underlying classical algorithm. We used local maximum in the fidelity landscape where the algo- asteepestascentgradientmethodsimilartotheclassical rithm gets stuck. Numerically we did not find this and Gradient Ascent Pulse Engineering (GRAPE) algorithm the protocol converged all the time provided the fidelity [26] which is commonly used in quantum control with was calculated to a high enough accuracy (this required great success. With extensive numerical optimisation accuracy is investigated in Fig. (4)). The lack of traps and simulations on a Python platform that we expanded is supported by recent results which state that, for well [30,31]wefindinFig. (4)thattoreachaC-NOTgatein behaved fidelity functions, a generic control system will anIsingchainofnqubitsthenumberofrunsofthesim- have no such traps [32, 33]. ulation required is N = O(n4). This efficient scaling tot is verified for systems of up to 7 qubits numerically. Ex- A future direction to take this work is to apply it to tending this to much larger systems is implausible due another important aspect of quantum computation, er- to the difficulty of simulating and optimising quantum rorcorrection. Theprotocoldetailedherecanbeusedin systems on a classical computers; the current numerical muchthesamewayforthisbyreplacingthetargetoper- data took the equivalent of 2 years of laptop computa- ationfromaC-NOTgate,tooneprotectingsomelogical tionaltime. Indeed,findingawayaroundthisisthevery qubits. Preliminary results show that with a tuneable advantageoftheinsitu optimisationscheme;testingthis interactionthesystemcandiscoverdecoherencefreesub- scaling relation for large systems would be an interest- spaces and simple error correcting codes this way. Work ing experiment that could only be done on a quantum remains on what the right tasks to ask of the simulator 4 Topology Coupling T N N are, and on showing the scalability of this approach. iters fids chain Ising π 60 120 The in situ optimal control scheme introduced here star Ising π 214 120 runs a classical optimisation algorithm on a quantum fully connected Ising 12π 295 1600 simulator in order to turn it into a universal quantum chain Heisenberg 16π 585 1600 computer. While the underlying algorithm we used was star Heisenberg 12π 1043 1600 gradientbased,manydifferentonescouldbeusedinstead fully connected Heisenberg 12π 881 1600 toimposedifferentconstraintsontheshapeofthecontrol pulse. All the evidence points towards the cost of doing this scaling polynomially with the size of the simulator, FIG. 5. The cost of performing the in situ optimisation makingsuchanapproachfeasibleforlargequantumsys- scheme is investigated for a range of different 5 qubit sys- tems. Akeyaspectofthisistoboundthegatefidelityof tems using the same numerical method as in Fig. (4). The differences between the systems are their topology (a lin- the whole system by the gate fidelities of single and two ear chain with nearest neighbour interactions, a star where qubit blocks, which can be measured efficiently. As well all interact with a central qubit only, or fully connected as upgrading quantum simulators into computer, it sug- where the interaction strengths are also randomised) and gests that it is not necessary to restrict architectures of the interaction type (Ising with σz⊗σz, or Heisenberg with quantumcomputerstothosewherecontrolscanbefound σx⊗σx+σy ⊗σy +σz ⊗σz). In each case the controls are analytically: having some interactions and local controls σ and σ on the single qubits, and the target operation is x y isenoughtoefficientlybootstrapaquantummachineinto a C-NOT gate on two qubits and identity on the rest. N iters a universal computer. is the average number of iterations required to achieve the 99.9%fidelitytarget. T isthetimeallowedforthesystemto This work was supported by EPSRC through the evolve, N and N are as in the main text and Fig. (4). reps fids Quantum Controlled Dynamics Centre for Doctoral We see that for all six systems the protocol can find the de- siredentanglinggate,anddoessoatreasonableexperimental Training, the EPSRC Grant No. EP/M01634X/1, and cost. Thisindicatesthattheapproachworksforawiderange the ERC Project ODYCQUENT. We are grateful to of possible quantum simulators. The case of the Ising chain HPCWalesforgivingaccesstotheclusterthatwasused and star are particularly easy for the scheme requiring a low to perform the numerical simulations. Many thanks to evolution time, number of iterations, and number of fidelity Stephen Glaser and David Leiner for discussions on pos- measurements per iteration. sible implementations. [1] D. DiVincenzo, arXiv:quant-ph/0002077 (2000). P.Roushan,A.Vainsencher,J.Wenner, andJ.M.Mar- [2] T. H. Johnson, S. R. Clark, and D. Jaksch, EPJ Quan- tinis, Phys. Rev. A 94, 032321 (2016). tum Technol. 1, 1 (2014). [12] J.Li,X.Yang,X.Peng, andC.-P.Sun,arXiv:1608.00677 [3] S. Machnes, U. Sander, S. J. Glaser, P. de Fouqui`eres, (2016). A. Gruslys, S. Schirmer, and T. Schulte-Herbru¨ggen, [13] P.Rebentrost,M.Schuld,F.Petruccione, andS.Lloyd, Phys. Rev. A 84, 022305 (2011). arxiv:1612.01789 (2016). [4] S. J. Glaser, U. Boscain, T. Calarco, C. P. Koch, [14] D. Lu, K. Li, J. Li, H. Katiyar, A. J. Park, G. Feng, W. Ko¨ckenberger, R. Kosloff, I. Kuprov, B. Luy, T.Xin,H.Li,G.Long,A.Brodutch,J.Baugh,B.Zeng, S.Schirmer,T.Schulte-Herbru¨ggen,D.Sugny, andF.K. and R. Laflamme, arxiv:1701.01198 (2017). Wilhelm, Eur. Phys. J. D 69 (2015). [15] D. Dong and I. R. Petersen, IET Control Theory Appl. [5] J. I. Cirac and P. Zoller, Nat. Phys. 8, 264 (2012). 4, 2651 (2010). [6] I. M. Georgescu, S. Ashhab, and F. Nori, Rev. Mod. [16] M.Johanning,A.F.Varo´n, andC.Wunderlich,J.Phys. Phys. 86, 153 (2014). B At. Mol. Opt. Phys. 42, 154009 (2009). [7] S. Lloyd, Phys. Rev. Lett. 75, 346 (1995). [17] B. P. Lanyon, C. Hempel, D. Nigg, M. Mu¨ller, R. Ger- [8] F. Albertini and D. D’Alessandro, Linear Algebra Appl. ritsma, F. Za¨hringer, P. Schindler, J. T. Barreiro, 350, 213 (2002). M.Rambach,G.Kirchmair,M.Hennrich, andP.Zoller, [9] D. J. Egger and F. K. Wilhelm, Phys. Rev. Lett. 112, Science (80-. ). 334, 57 (2011). 240503 (2014). [18] R. Blatt and C. F. Roos, Nat. Phys. 8, 277 (2012). [10] J. Kelly, R. Barends, B. Campbell, Y. Chen, Z. Chen, [19] I.Bloch,J.Dalibard, andS.Nascimb`ene,Nat.Phys.8, B.Chiaro,A.Dunsworth,a.G.Fowler,I.C.Hoi,E.Jef- 267 (2012). frey, A. Megrant, J. Mutus, C. Neill, P. J. J. O’Malley, [20] H. Labuhn, D. Barredo, S. Ravets, S. de L´es´eleuc, C. Quintana, P. Roushan, D. Sank, A. Vainsencher, T. Macr`ı, T. Lahaye, and A. Browaeys, Nature 534, J. Wenner, T. C. White, a. N. Cleland, and J. M. Mar- 667 (2016). tinis, Phys. Rev. Lett. 112, 240504 (2014). [21] X.H.PengandD.Suter,Front.Phys.China5,1(2010). [11] J. Kelly, R. Barends, A. G. Fowler, A. Megrant, E. Jef- [22] J. Cai, A. Retzker, F. Jelezko, and M. B. Plenio, Nat. frey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Phys. 9, 168 (2013). Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, E. Lucero, [23] J.Geng,Y.Wu,X.Wang,K.Xu,F.Shi,Y.Xie,X.Rong, M. Neeley, C. Neill, P. J. J. O’Malley, C. Quintana, and J. Du, Phys. Rev. Lett. 117, 170501 (2016). 5 [24] J. L. Dodd, M. A. Nielsen, M. J. Bremner, and R. T. from a Hamiltonian H = (cid:80)ihi ⊗1¯i such that each hi Thew, Phys. Rev. A 65, 040301 (2002). acts on its own part of the Hilbert space and is iden- [25] J.F.Poyatos,J.I.Cirac, andP.Zoller,Phys.Rev.Lett. tity on the rest. This has a single 0 eigenvalue E with 0 78, 390 (1997). eigenstate|ψ(cid:105), whileallitsothereigenvaluesarepositive [26] N.Khaneja,T.Reiss,C.Kehlet,T.Schulte-Herbru¨ggen, integers. ByexpandingthisHamiltonianinitseigenbasis and S. J. Glaser, J. Magn. Reson. 172, 296 (2005). we have [27] M. P. Da Silva, O. Landon-Cardinal, and D. Poulin, Phys. Rev. Lett. 107, 210404 (2011). (cid:88) Tr[Hρ]= E (cid:104)E |ρ|E (cid:105) [28] A. Gilchrist, N. K. Langford, and M. a. Nielsen, Phys. k k k Rev. A 71, 062310 (2005). k≥0 [29] M.Cramer,M.Plenio,S.Flammia,R.Somma,D.Gross, (cid:88) ≥ (cid:104)E |ρ|E (cid:105) S.Bartlett,O.Landon-Cardinal,D.Poulin, andY.Liu, k k Nat. Commun. 1, 149 (2010). k>0 [30] J. R. Johansson, P. D. Nation, and F. Nori, Comput. ≥1−(cid:104)ψ|ρ|ψ(cid:105) Phys. Commun. 184, 1234 (2013). F(M,U)=(cid:104)ψ|ρ|ψ(cid:105)≥1−Tr[Hρ] [31] R. Johansson, P. Nation, A. Pitchford, C. Granade, A. L. Grimsmo, Markusbaden, A. Vardhan, P. Migdal(cid:32), TheexpectationvalueoftheHamiltoniancanbeeval- Kafischer, D. Vasilyev, B. Criger, J. Feist, Alexbrc, uated according to F. Henneke, D. Meiser, F. Ziem, Nwlambert, S. Kras- tanov, R. Brierley, R. Heeres, J. Ho¨rsch, Qi, S. Whalen, (cid:88) N. Tezak, J. Neergaard-Nielsen, E. Hontz, Amit, and Tr[Hρ]= Tr[(1 −|ψ (cid:105)(cid:104)ψ |)ρ] i i i Adriaan, “QuTiP-4.0.0,” (2016). i [32] T.S.Ho,J.Dominy, andH.Rabitz,Phys.Rev.A-At. (cid:88) = (1−(cid:104)ψ |ρ |ψ (cid:105)), Mol. Opt. Phys. 79, 013422 (2009). i i i [33] B. Russell, H. Rabitz, and R. Wu, arxiv:1608.06198 i (2016). where ρ =Tr [ρ]. This is also the Choi state of the map i i M (·)=M(· (cid:78) 1 1 ), which results in Eq. (1) i j(cid:54)=i dj j APPENDIX - LOCAL ESTIMATOR OF THE FIDELITY F(M,U)≥1−(cid:88)(1−F(M ,U )). i i i We derive a bound for the gate fidelity F(M,U) = (cid:104)ψ|ρ |ψ(cid:105) where |ψ(cid:105)(cid:104)ψ| = U ⊗id|Ω(cid:105)(cid:104)Ω| and ρ = M ⊗ One way of measuring F is to prepare the state of M LE id|Ω(cid:105)(cid:104)Ω| are the Choi states of U and M respectively, onesubspaceinabasisstateandalltheothersinamax- given by those expressions, where id is the identity map imally mixed state, perform the simulation, measure the (cid:80) and |Ω(cid:105) = |kk(cid:105) is a maximally entangled state be- initial subspace, and then repeat for a tomographically k tween the original and doubled space. We consider the complete basis set and for each subsystem; giving a cost case where the target operation U is unitary and has a of N = (cid:80) O((d )2) = O(n). However by noting (cid:78) meas i i tensorproductstructuresuchthatU = U . TheChoi that a maximally mixed state is a random mixture of i(cid:78)i state of U has the same structure |ψ(cid:105) = |ψ (cid:105) where pure states, the fidelity of each subsystem can be mea- i i each |ψ (cid:105) is on the doubled Hilbert space of U . suredatthesametimebypreparingeachoneinarandom i i TofindaboundforF(M,U)webeginbyconstructing pure basis state. In this case there is no scaling with the the projectors h = 1 −|ψ (cid:105)(cid:104)ψ | for each tensor com- number of qubits as the number of repetitions required i i i i ponent of U. These have a single 0 eigenvalue, and the depends only on the size of the largest subsystem, which others are 1. These projectors are grouped together to gives N =O(1). meas