Table Of Content

Efficient quantum state tomography Marcus Cramer and Martin B. Plenio Institut fu¨r Theoretische Physik, Albert-Einstein Allee 11, Universita¨t Ulm, 89069 Ulm, Germany Steven T. Flammia and Rolando Somma Perimeter Institute for Theoretical Physics, Waterloo, Ontario, N2L 2Y5 Canada David Gross Institute for Theoretical Physics, Leibniz University Hannover, 30167 Hannover, Germany Stephen D. Bartlett School of Physics, The University of Sydney, Sydney, New South Wales 2006, Australia 1 Olivier Landon-Cardinal and David Poulin 1 D´epartement de Physique, Universit´e de Sherbrooke, Sherbrooke, Qu´ebec, Canada 0 2 Yi-Kai Liu n Institute for Quantum Information, California Institute of Technology, Pasadena, CA, USA a J Quantumstatetomography[1],theabilitytodeducethestateofaquantumsystemfrommeasured 3 data,isthegoldstandardforverificationandbenchmarkingofquantumdevices. Ithasbeenrealized 2 in systems with few components [2–7], but for larger systems it becomes infeasible because the numberofquantummeasurementsandtheamountofcomputationrequiredtoprocessthemgrows ] exponentiallyinthesystemsize. Hereweshowthatwecandoexponentiallybetterthandirectstate h p tomography for a wide range of quantum states, in particular those that are well approximated by - a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems t and touch on generalizations. One scheme requires unitary operations on a constant number of n subsystems, while the other requires only local measurements together with more elaborate post- a u processing. Both schemes rely only on a linear number of experimental operations and classical q postprocessingthatispolynomialinthesystemsize. Afurtherstrengthofthemethodsisthatthe [ accuracy of the reconstructed states can be rigorously certified without any a priori assumptions. 1 v I. INTRODUCTION ofsamples. Assumingonewereabletocollectallthedata 6 from an informationally complete measurement, one is 6 left with the intractable computational task of inverting 3 One of the principal features distinguishing classical 4 themeasuredfrequenciestofindanestimateofthestate. from quantum many-body systems is that quantum sys- . However, the traditional representation of quantum 1 tems require exponentially many parameters in the sys- states is in a sense too general. Indeed, states which oc- 0 tem size to fully specify the state, compared to only lin- 1 cur in many practical situations are specified by a small early many for classical systems. Put to use construc- 1 number of parameters. An efficient description could be tively, the exponential complexity enables the construc- : a practical preparation scheme which outputs the state; v tion of information processing devices fundamentally su- or, in the case of thermodynamical equilibrium states, a i X perior to any classical device. At the same time, how- localHamiltonianandatemperature. Thisinsightisnot ever, this “curse of dimensionality” makes engineering r new: researchers in many-body physics and quantum in- a tasks—suchasverifyingthatthequantumprocessingde- formationtheoryhavefoundmanyclassesofstateswhich vice functions as intended—a daunting challenge. are described by a number of parameters scaling polyno- The full determination of the quantum state of a sys- mially in N [9–13] and which closely approximate the tem, known as quantum state tomography [1], has al- kind of states found in physical systems [14, 15]. How- ready been achieved by measuring a complete set of ob- ever, the question of whether these restricted classes can servables whose expectation values determine the quan- beputtouseinthecontextoftomographyhasremained tum state [2–7]. As it is typically formulated [8], simply largely open. to output an estimate for a generic state would take ex- In this work, we address the above challenge. The ponentialtimeinthesystemsizeN, giventhatthereare physical system we have in mind is one where the con- an exponential number of coefficients in a generic state’s stituents are arranged in a one-dimensional configura- description. Thisisbutoneofseveralinefficiencies. Most tion (e.g., ions in a linear trap [3]). But the methods quantum states have exponentially small amplitudes in thatwearepresentingherecanbegeneralizedtohigher- almosteverybasis,sotodistinguishanyoneofthoseam- dimensional arrangements such as those realized in opti- plitudesfromzero,onemusttakeanexponentialnumber cal lattices [16]. It is highly plausible that in such a set- 2 ting,correlationsbetweenneighboringparticlesaremuch more pronounced (due to direct interaction) than corre- lations between distant systems (mediated e.g. by global fluctuations of control fields). An efficiently describable classofstatesanticipatingexactlythisbehaviorhaslong beenstudiedunderthenamesoffinitelycorrelatedstates (FCS) or matrix product states (MPS) [9, 10]. Impor- tantly, restricting to this class is not a limitation since every statemaybewrittenasaMPSwithasuitable, al- beitpossiblylarge, matrixdimension. Sincemanystates that are relevant for quantum information processing or quantum many-body physics have a small (independent ofN)bonddimension, ourmethodsaredirectlyapplica- ble to such states; examples include, but are not limited to, groundandthermalstates, theGHZ,W,cluster, and AKLT states, the latter two being universal resources states for quantum computing. FIG. 1. Quantum circuit that transforms |φ(cid:105) into Given that standard tomography is no longer feasible |0(cid:105)⊗N−κ+1 ⊗|η(cid:105) with κ = 3. The unitaries Uˆ successively inarangeofrecentandupcomingexperimentsinvolving i disentangle the particles and the state |η(cid:105) on the last sites large numbers of qubits, our results represent a signifi- acts as a boundary condition to determine the MPS descrip- cant advance in the ability to verify and quantitatively tion of |φ(cid:105). and efficiently benchmark systems of experimental im- portance. σˆ tr [(cid:37)ˆ]. This reduced density matrix has the κ+1,...,N ≈ eigendecompositionσˆ = R σ φ φ wheretherank II. RESULTS r=1 r| r(cid:105)(cid:104) r| R dκ 1. Hence there exists a density matrix with one − ≤ (cid:80) fewerquditthathasthesamerankR andeigenvaluesσ r In the following we present two schemes for identify- asσˆ. Thereforewecandisentanglethefirstsiteinσˆ with ing systems that are well approximated by an MPS, ini- the following unitary acting on the first κ sites: tiallyfocusingonpurestatesforsimplicity. Wewillview each system as consisting of a linear chain of N qudits, d 1dκ−1 1 eachhavingdimensiond. Bothschemesrequirethemea- Uˆ = − − s s φ , (1) surement of linearly (in the system size N) many local | (cid:105)1⊗| (cid:48)(cid:105)2,...,κ(cid:104) sdκ−1+s(cid:48)+1|1,...,κ s=0 s(cid:48)=0 observables within finite accuracy, polynomial classical (cid:88) (cid:88) post-processing of the data and can certify the accuracy where φ ,..., φ have been extended in some arbi- 1 R | (cid:105) | (cid:105) of the reconstructed state without making any technical trary way to get a complete basis for sites 1,...,κ. Ap- assumptions about the state in the laboratory. The first plyingUˆ producesthestateUˆ φ = 0 v ,where 1 2,...,N | (cid:105) | (cid:105) ⊗| (cid:105) scheme requires unitary control and local measurements v is some pure state on sites 2,...,N. Hence Uˆ disen- while the second scheme removes the need for unitary |ta(cid:105)nglesthefirstquditfromalltheothers. Now,setaside control at the cost of more elaborate post-processing. this first qudit, look at sites 2,...,κ+1, and repeat the aboveprocessasindicatedonFig.1. Inthisway,oneob- tainsasequenceofunitariesUˆ ,...,Uˆ ,whereeach 1 N κ+1 A. Scheme based on unitary transformations Uˆ actsonsitesi,...,i+κ 1. Thisseq−uencetransforms i φ into Uˆ Uˆ φ −= 0 N κ+1 η , where η N κ+1 1 ⊗ − The key idea of the method consists of a sequential i|s(cid:105)some pure−stat·e·o·n t|he(cid:105)last| κ(cid:105) 1 sites⊗. | (cid:105) | (cid:105) − procedure to disentangle the left hand side of the chain In summary, this scheme infers the quantum circuit from the right hand side, using a sequence of unitary usedtoprepareanMPS[17]. TheMPSdecompositionof operations with small interaction length independent of φ canthenbeobtainedreadilyfromtheU and η [18]. i | (cid:105) | (cid:105) N. The result will be a product state and a sequence If the state in the laboratory (cid:37)ˆ is arbitrary, then the of local unitary operations from which to construct the reduced density matrices σˆ will generally have full rank. original state. Hence in each step we will need to truncate the κ qudit Supposetheidealstateinthelaboratoryis(cid:37)ˆ= φ φ, state σˆ to a rank R subspace with R < dκ 1. Then the − | (cid:105)(cid:104) | which we assume for clarity is a MPS of given bond di- above method will produce an MPS approximation to (cid:37)ˆ. mension. This implies that the rank of reductions to The accuracy of this estimate can be certified, without one part of a bipartite (left vs. right) split of the chain any assumptions on the state, by keeping track of the is bounded by a constant R. The protocol starts by effects of truncating each of the reduced states σˆ. As estimating, through standard state tomography, the re- shownintheMethods,errorsofmagnitude(cid:15)duetofinite duced density matrix of the first κ= log (R) +1 sites, measurement precision or truncation error (as measured (cid:100) d (cid:101) 3 bytheweightofthetruncatedspace)accumulateatmost closetotheσˆ . A priori itisunclearwhethersuchacon- i linearly with the number of sites, and can be evaluated venient witness always exists and how it could be found directlyfromthedata,leadingtoanestimateofaccuracy efficiently. However,usingformalmethods,onecanshow N(cid:15). that if the true state (cid:37)ˆ is close to a generic MPS, then Thepresentschemerequiresunitarycontrolofκneigh- such a witness Hamiltonian always exists [10]. What is boringqudits,whichischallengingtoimplementinmany more,itcanbeconstructedfromtheestimateofthealgo- current experimental settings. We now present a second rithm sketched below. Its properties, chief among them scheme that avoids unitary control and requires only lo- the gap, are efficiently computable. In the Methods sec- cal measurements. tion, we detail the efficient computation of these quan- tities, and we also consider how to treat states such as the GHZ for which local marginals alone are not quite B. Scheme based on local measurements: sufficient for complete characterization (they violate our Certification of estimated state “generic” condition). Consider again the state (cid:37)ˆin the laboratory and sup- pose that a tomographically-complete set of local mea- surements on all groups of k neighbouring qubits has C. An illustrative example beenperformed. Furthersupposethatsufficientdatahas been taken to yield estimates σˆ of the local reductions i (cid:37)ˆi =tr1,...,i;i+k+1,...,N[(cid:37)ˆ] such that We illustrate how our certification procedure operates if our estimate for the state (cid:37)ˆ is a linear cluster state (cid:37)ˆ σˆ (cid:15) . (2) i i tr i [20]. Theclusterstateisdefinedastheuniqueeigenstate (cid:107) − (cid:107) ≤ (with eigenvalue +1) of stabilizers Kˆ = Zˆ Xˆ Zˆ Determining these approximate reduced density opera- i i 1 i i+1 for all i = 2,...,N 1 (together with bounda−ry terms tors σˆi completes the experimental work. In the remain- Xˆ Zˆ andZˆ Xˆ ,−whichwedonottreatseparatelyfor derwedescribetheclassicalpost-processingthatwillre- 1 2 N 1 N simplicity). A−ssume that we have performed standard sultinaMPSestimate ψ to(cid:37)ˆandalowerboundtothe | (cid:105) quantum state tomography on sets of three neighbour- fidelity ψ (cid:37)ˆψ [19]thatdoesnotrequireassumptionson (cid:104) | | (cid:105) ing spins, k =3, which is the smallest useful set because the nature of the state (cid:37)ˆ. in a cluster state the rank of the reduced density ma- We start with the latter, since the following easy trices of contiguous blocks is upper bounded by R = 4. calculation yields the fidelity bound we have in mind Let us now assume that on the basis of these data, our and hints at the MPS estimate we are after. Suppose, procedure suggests that the linear cluster state is indeed for the sake of the argument, that ψ is the unique | (cid:105) our estimate. The local Hamiltonian in this case is given ground state (with energy zero) of a local Hamiltonian Hiˆng=onlyiohˆni,siwtehserie+t1h,e..hˆ.i,iis+akp(raosjeitcttiuornnsopoeurta,tgoernaecritc- bpyroHjˆect=ors,iHˆ(1h−asKˆtih)e/2c,luwstheerresttahtee (a1s −itsKˆuin)i/q2ue=ghˆroiuanrde (cid:80) MPSa(cid:80)reofthistype). Then,expandingintheeigenbasis state(withenergyzero)andanenergygap∆E =1. The Hˆ = 2nN=−01En|En(cid:105)(cid:104)En|, fibdouelnitdyedbebtyweeψnth(cid:37)eˆcψluster=st1ate|ψC(Str(cid:105)[hˆanσˆd]t+he(cid:15)s)t,atweh(cid:37)ˆeries (cid:104) CS| | CS(cid:105) − i i i i tr[(cid:80)Hˆ(cid:37)ˆ]≥∆E (cid:104)En|(cid:37)ˆ|En(cid:105)=∆E(1−(cid:104)ψ|(cid:37)ˆ|ψ(cid:105)), (3) t(cid:15)ailfreormrorEinq.t(h3e)loqcuaalnetxifipeesritmheensttaa(cid:80)ltiessttiicmalataensd,aenxdpetrri[mhˆeσˆn-] i i n>0 (cid:88) quantifieshowmuchthelaboratorystate(cid:37)ˆdeviatesfrom where we denoted by ∆E the energy gap above the an exact cluster state. ground state ψ . Hence, we have the fidelity bound Tomography on a cluster state can also be performed | (cid:105) with the scheme based on unitary transformations. A tr[h ρˆ] 1 ψ (cid:37)ˆψ 1 i i 1 tr[hˆ σˆ ]+(cid:15) . cluster state is the output of a quantum circuit where i i i (cid:104) | | (cid:105)≥ − ∆E ≥ − ∆E each qubit is initially prepared in the state + = (cid:80) (cid:16)(cid:88)i ((cid:17)4) 1/√2 0 + 1 and a controlled phase transform| a(cid:105)tion | (cid:105) | (cid:105) CZ acts successfully on each pair of neighboring qubits. In other words, the Hamiltonian acts as a witness for its The C(cid:0)Z gate (cid:1)changes the sign of state 11 and acts | (cid:105) ground state ψ . This bound is tight: suppose the ex- trivially on the other states of the computational basis. | (cid:105) perimental estimates σˆi and the reductions of the state Thus, a cluster state is the output of a circuit whose in the laboratory (cid:37)ˆi coincide, that is (cid:15)i = 0. If, in addi- structurecorrespondstotheoneindicatedonFig.1with tion, the reductions of ψ match the σˆi then, as ψ was κ = 2 and the scheme based on unitary transformations | (cid:105) | (cid:105) assumed to be the unique ground state with energy zero directly applies. Note that the unitary scheme takes ad- of hˆ , we have tr[hˆ σˆ ]=0, i.e., ψ (cid:37)ˆψ =1. vantageofthedecreasedrankofareduceddensitymatrix i i i i i (cid:104) | | (cid:105) The goal is now clear: find a local gapped Hamilto- on the boundary to save one qubit worth of local tomo- nia(cid:80)n Hˆ such that (cid:80)the reductions of its ground state are graphic effort (κ=2 vs. k =3). 4 D. Scheme based on local measurements: Efficient 1 determination of an MPS estimate 700 1−fN,n With the experimentally obtained σˆ , we now turn to i the task of finding an MPS ψ such that its reductions | (cid:105) 500 tr [ψ ψ ] closely match the σˆ . In other 1,...,i;i+k+1,...,N i | (cid:105)(cid:104) | words: Let Pˆi,k be all possible products of Pauli oper- m ators (enumerated by m) that act non-trivially only on 300 sites i+1,...,i+k. Then, as the Pˆi are an orthogonal m basis, the σˆ may be expanded as i σˆi = 21N tr[σˆiPˆmi ]Pˆmi , (5) 100 1 812 m 1 102 1 (cid:88) 400 300 1 122 N2 where the expectations tr[σˆPˆmi ] ∈ R are obtained as re- n 200 100 3102162 sults of tomographic measurements. Then we need to find a matrix ψ ψ such that for all m and i the ex- FIG. 2. Performance of the MPS-SVT algorithm for the pectations tr[ψ| (cid:105)ψ(cid:104) Pˆ|i ] coincide with those of the tomo- groundstate(thetargetstate|φ(cid:105))ofthecriticalIsingmodel. | (cid:105)(cid:104) | m We chose k = 2, i.e., only nearest neighbour reductions are graphic estimates, tr[ψ ψ Pˆi ]=tr[σˆ Pˆi ]. | (cid:105)(cid:104) | m i m used to reconstruct the state. Plot illustrates the scaling of The method of choice for such a problem is singular theerrorinthefidelity1−f =1−|(cid:104)φ|y (cid:105)|2 ∼N2/nwith N,n n value thresholding (SVT) [21, 22], which has been devel- the number of spins N and the iterations n of the algorithm. oped very recently in the context of classical compres- sive sampling or matrix completion [23] and may also be applied to the quantum setting [24–28]. SVT is a re- These numerical examples suggest convergence of our cursive algorithm that provably converges to a low-rank algorithmtoaMPSthatcloselymatchestheexperimen- matrix satisfying constraints of the type tr[|ψ(cid:105)(cid:104)ψ|Pˆmi ] = tally obtained reductions σˆi. To arrive at the fidelity tr[σˆiPˆmi ]. Unfortunately,astraightforwardapplicationof bound we follow the steps of Section IIB: (i) Obtain es- SVT requires time and memory that scale exponentially timates σˆ of the reductions to k adjacent spins (cid:37)ˆ of the i i withthenumberofparticles. However, amodificationof state in the laboratory such that σˆ (cid:37)ˆ (cid:15) , (ii) i i tr i (cid:107) − (cid:107) ≤ the algorithm allows us to overcome this problem. compute the expectations p =tr[σˆ Pˆi ], which are the Giventhemeasuredvaluestr[σˆiPˆmi ]thealgorithmmay input to the MPS-SVT algomriithm, (iiii)mobtain a MPS es- then be described as follows. First set up the operator timate y , the reductions of which closely match the Rˆ = m,itr[σˆiPˆmi ]Pˆmi /2N andinitializeYˆ0 tosomearbi- σˆi by u|tilniz(cid:105)ing the MPS-SVT algorithm. As yn is an | (cid:105) trarymatrix(e.g.,thezeromatrix). Thenproceedrecur- MPS, one can then efficiently obtain a parent Hamilto- (cid:80) sively by finding the eigenstate yn with largest eigen- nian [10]andalowerbound,∆,ontheenergygapabove | (cid:105) value, y , of Yˆ and set the ground state (see Methods for details). Putting all n n this together, the above programme returns a state y , Xˆn =yn (cid:104)yn|P2ˆNmi |yn(cid:105)Pˆmi , (6) itthsaptarentHamiltonianHˆ = ihˆi,andanumber∆|sunc(cid:105)h (cid:88)m,i (cid:80) Yˆn+1 =Yˆn+δn(Rˆ−Xˆn). y (cid:37)ˆy 1 i((cid:15)i+tr[hˆiσˆi]). (7) n n Sofar,thisalgorithmstillsuffersfromthefactthatinev- (cid:104) | | (cid:105)≥ − ∆ (cid:80) erystepthe2N 2N matrixYˆ needstobediagonalized. n However, theYˆ×areoftheform M a Pˆi , a R, n m,i m,i m m,i ∈ wherethePˆi actnon-triviallyonlyonsitesi+1,...,i+k, m (cid:80) i.e., theyhavetheformofalocal“Hamiltonian”. Hence, E. Example: Strongly interacting quantum systems y can be determined as the highest energy state of n | (cid:105) this Hamiltonian. For this task standard methods have Westartwithgroundstatesofnearest-neighborHamil- been developed in condensed matter physics [13, 29] for tonians on a chain, i.e., the φ = gs are completely de- | (cid:105) | (cid:105) which the number of parameters scale polynomially in termined by all the reductions to two adjacent spins and the system size and converge rapidly [30, 31] to the op- weexpecttheabovealgorithmnotonlytoproducestates timal MPS approximation. The standard but exponen- that match the reduced density matrices of the ground tially inefficient SVT algorithm possesses a convergence statesbut,infact,statesthatarethemselvesclosetothe proof while our efficient modification does not. Hence, ground states. Among ground states of one-dimensional we now present numerical examples for different target nearest-neighbor Hamiltonians, those at a critical point states φ to demonstrate the feasibility and efficiency of arethemostchallengingtoapproximatebyMPSasthey | (cid:105) the proposed algorithm. violate the entanglement area law [32]. We demonstrate 5 determine the ground state gs (our target state φ ) | (cid:105) | (cid:105) and its reductions and then computed the fidelity f N,n 1 fN,n after n iterations of the MPS-SVT algorithm, see Fig. 3. − ￿ F. Example: W-state preparation in ion traps 0.2 Ourmethodisofinterestformanysituationsinwhich standard tomography will not be feasible. This is the case for the verification of state preparation in experi- mentswithtoomanyparticles. Anexampleistherecent 0.1 ion trap experiment [3] for the preparation of W-states, φ = (10 0 + 010 0 + + 0 01 )/√N, that | (cid:105) | ··· (cid:105) | ··· (cid:105) ··· | ··· (cid:105) were limited to 8 qubits principally because the classi- cal postprocessing of data became prohibitive for longer chains. Here we demonstrate the efficiency of our ap- 15 20 25 30 N proach (we are not limited to few ions and demonstrate convergence for up to 20 ions – even higher number of ions are easily accessible due to the MPS alteration of theSVTmethod)byillustratinghowonewouldpostpro- FIG. 3. Fidelity fN,n =|(cid:104)φ|yn(cid:105)|2, for a fixed value n=5, as cessexperimentallyobtainedreduceddensitymatricesto afunctionofthenumberofspinsN forthegroundstate(the guaranteethegenerationof φ orastateveryclosetoit. targetstate|φ(cid:105))oftherandomnearest-neighbourHamiltoni- | (cid:105) Notethat,asintheabovespinchainexamples,oneneed ans of Eq. 8. As in Fig. 2, we chose k=2 to reconstruct the only take tomographic data on pairs (k = 2) of neigh- state. The plot shows densities (arrows indicate the mean) bouring qubits. We mimic experimental noise by adding obtained from 1000 random realizations. Similar to the Ising model,thescalingforfixednof1−f isbetterthan∼N2. Gaussian distributed random numbers with zero mean N,n to the p . After initializing the algorithm with Yˆ =Rˆ, mi 0 where we obtain Rˆ from the MPS representation of φ , | (cid:105) the effectiveness of our algorithm for such an example: weusex := p y Pˆi,k y asafigureofmerit the critical Ising model in a transverse field on a chain for convenrgence,mii.e|.,ma,if−te(cid:104)r an|gimven| nn(cid:105)u|mber of iterations, oflengthN withopenboundaryconditions. Theground we pick the y(cid:80) with minimum x . The result of such a n n state of this Hamiltonian is unique and hence it is com- procedure is|sh(cid:105)own in Fig. 4. pletely characterized by its reductions to k = 2 neigh- bouringsites. Inotherwords,ifwefindanMPSthathas thesamereductions,thefidelitywillbeone. Weproceed III. DISCUSSION as follows. (i) We obtain the reductions (cid:37)ˆ to two neigh- i bouring sites of the true ground state, (ii) from these Wehavepresentedtwoschemesthatefficientlyproduce reductions we obtain the expectations pmi = tr[(cid:37)ˆiPˆmi], anMPSdescriptionasatomographicestimateofaquan- whicharetheinputtotheMPS-SVTalgorithm. InFig.2 tum state, along with a tight fidelity bound. We empha- we show the fidelity fN,n = yn φ 2 of the true ground size that no assumptions are necessary for our scheme; if |(cid:104) | (cid:105)| state φ and the n’th iterate of the above algorithm as nosuchMPSdescriptionexists,thiswillbeevidentfrom | (cid:105) a function of n and the length N of the chain. It shows the local tomographic data and our schemes will herald that for fixed system size 1 fN,n decreases as 1/n a failure. However, the enormous successes of MPS for − ∼ while for fixed n it increases slower than N2. This pro- describingbothone-dimensionalquantumsystemsfound vides an indication that our algorithm is polynomial in in nature as well as a host of states relevant to quantum the system size. informationensuresthatourmethodswillbeveryuseful The Ising model is solvable and, in order to show that in practice. we are not considering a special case that is particu- Sofarwepresentedthemethodforpurestatesandone- larly favourable, we also consider one-dimensional ran- dimensional systems. Various generalizations are pos- dom Hamiltonians of the form sible: Our first scheme using unitary control can also handle mixed states corresponding to small ensembles N 1 Hˆ = − rˆ(i)rˆ(i) , (8) of pure MPS. Suppose we are presented with a state (cid:37)ˆ i i+1 that is a mixture of M pure states, each of which is an i=1 (cid:88) MPS having bond dimension D. Then the reduction of where the rˆ(i), rˆ(i) act on spin i and i+1, respectively, (cid:37)ˆto any subsystem has rank at most MD. We can pro- i i+1 and are hermitian matrices with entries that have real ceed as before, performing unitary operations on blocks and imaginary part picked from a uniform distribution of κ = log (MD) +1 sites, in order to disentangle in- (cid:100) d (cid:101) over [ 1,1]. For each Hamiltonian, as before, we first dividual sites from the rest of the chain. At the end of − 6 fN,n tended to mixed states by considering purifications and can then, e.g., also handle thermal states of local Hamil- tonians,underthephysicallyreasonableassumptionthat theentropydensityexists[33]. Inaddition,itcanbegen- 0.98 eralized to all mixed finitely correlated states (FCS) [9], though it is not always possible to certify the resulting estimates. Higher-dimensional systems are more challenging, be- 0.96 cause the most straightforward generalization of MPS, known as projected entangled-pair states (PEPS) [34], cannot be computed as efficiently. However, the certifi- 0.94 cation method using a frustration-free parent Hamilto- nian remains efficient in the case of qubits with nearest- neighbor couplings [35]. Combinations of our techniques can be used to reconstruct other classes of states, such 0.92 as tree tensor networks [36] and multiscale entanglement 10 15 20 N renormalizationansatz(MERA)states[37],forwhichef- ficient heuristics for minimizing local Hamiltonians are FIG. 4. Performance of the MPS-SVT algorithm√for W- available. states,|φ(cid:105)=(|10···0(cid:105)+|010···0(cid:105)+···+|0···01(cid:105))/ N. We are not limited to few ions and demonstrate convergence for up to 20 ions – even higher number of ions are easily acces- ACKNOWLEDGMENTS sible due to the MPS alteration of the SVT method, demon- stratingtheefficiencyofourapproach. Wemimicexperimen- tal noise by adding Gaussian distributed random numbers The authors acknowledge discussion with F.G.S.L. withzeromeantothelocalexpectationsp =tr[σˆ Pˆ ]and Brand˜ao at early stages of this project. The work at mi i mi show results for n = 4000 MPS-SVT iterations. Plot shows UlmUniversityhasbeensupportedbytheEUIntegrated fN,n =|(cid:104)φ|yn(cid:105)|2asafunctionofthenumberofions,N,forno Project QAP, the EU STREP’s CORNER and HIP and noise (dots) and Gaussian noise (densities obtained from 100 an Alexander von Humboldt Professorship. SDB ac- realizations for each N, arrows indicate mean) with a stan- knowledgesthesupportoftheAustralianResearchCoun- dard deviation of 0.005 (blue; only even values of N plotted cil and the Perimeter Institute. STF and RS were sup- for clarity) and 0.01 (black, odd N). portedbythePerimeterInstituteforTheoreticalPhysics. ResearchatPerimeterissupportedbytheGovernmentof CanadathroughIndustryCanadaandbytheProvinceof the chain, we will find a mixed state η of rank M on the Ontario through the Ministry of Research & Innovation. lastκ 1sites. Wedecomposeη asamixtureofM pure − DG is glad to acknowledge support from the EU (COR- states. Thisyieldsarepresentationof(cid:37)ˆasanensembleof NER).OLCandDParepartiallyfundedbyNSERCand M pure MPS, each with bond dimension at most dMD. FQRNT. YKL is funded by the US ARO/NSA. Our second scheme using local measurements can also beextendedtohandlemixedstates. Whilethek-particle reduced density matrices do not uniquely determine the IV. METHODS mixed state (cid:37)ˆ, reconstructions of better and better qual- ity can be obtained by increasing k. As an example, suppose (cid:37)ˆ is the Gibbs state corresponding to a k-local WestartbyrecallingtheMPSrepresentationofastate HamiltonianHˆ, i.e. thestateminimizingthefreeenergy ψ withopenboundaryconditions(generalisationstope- | (cid:105) riodic boundary conditions are entirely straightforward). tr[(cid:37)ˆHˆ] TS((cid:37)ˆ). (9) − d1−1 dN−1 The first term is, as before, determined by the reduced ψ = M1[s1] MN[sN]s1 sN , (10) | (cid:105) ··· ··· | ··· (cid:105) density matrices. The entropy of the total state how- s(cid:88)1=0 s(cid:88)N=0 ever can only be learned exactly from the complete den- where the M [s] are D D matrices with D = sity matrix. Yet, for essentially all reasonable physical i i i+1 1 × D = 1. We denote the bond dimension by D = systems, the entropy density lim S(tr ((cid:37)ˆ))/k in N+1 k k+1,... the thermal state of a Hamiltonia→n∞exists [33] (In partic- maxDi. ular, finitely correlated states are precisely those states whoseentropydensityisexactlyequaltoS(tr ((cid:37)ˆ)) k+1,... S(tr ((cid:37)ˆ))forsomefinitevalueofk). Asaconsequenc−e, A. Direct tomography k,... thetotalentropyofthestatecanbeestimatedefficiently from knowledge of the reduced density matrices. Hence, This method proceeds by disentangling all the qudits our second scheme using local measurements may be ex- of the chain sequentially. Thus, it yields a valid MPS 7 description if every unitary exactly disentangles one qu- be dit. Put another way, while it is crucial to obtain a good estimate of the dκ−1-dimensional subspace on which σˆ is Uˆ Uˆ ...Uˆ φ = |0(cid:105)⊗i⊗Uˆi+1|ηi(cid:105)+Uˆi+1|ecim(cid:105) (13) i+1 i 1 supported,itisnotnecessary toidentifytheeigenvectors | (cid:105) 1+ ecm ecm (cid:104) i | i (cid:105) of σˆ exactly : any set of orthonormal vectors generating 0 i+1 η + ecm the subspace is sufficient for our tomography procedure = | (cid:105)⊗ (cid:112)⊗| i+1(cid:105) | i+1(cid:105) (14) and leads to an MPS description in another gauge [10]. 1+ ecm ecm (cid:104) i+1| i+1(cid:105) This property will be central to our error analysis. (cid:113) Tounderstandtheeffectoferrorsandimperfectionsin where our tomography procedure, consider the very first step e +U ecm of the recursive procedure. Tomography is performed on ecm = | i(cid:105) i+1| i (cid:105) (15) | i+1(cid:105) 1+ ecm ecm the first κ sites to ideally find a state with non-maximal (cid:104) i | i (cid:105) support, and unitary Uˆ1 is applied to rotate that state and therefore (cid:15)cm (cid:15)cm(cid:112)+(cid:15) . into the subspace cutoff = 0 (Cd) n 1. In any ex- i+1 ≤ i i+1 H1 | (cid:105)⊗ ⊗ − Thus, we see that errors accumulate linearly with perimentalsetting,theresultingstateUˆ1 φ wouldsurely the number of particles; if we denote ψ = ncaoutsleietheentsitraetlyeoinftthheatsyssutbemspaiscen.otTehxisaccta|lyn(cid:105)abneMeitPhSerwbiteh- hUˆa1†v.e..UˆN†−κ+1|0(cid:105)N−κ+1|ηN−κ+1(cid:105)theestimatedM|P(cid:105)S,we bond dimension D, but merely close to one or because our estimate of the density matrix σˆ on sites 1 to κ is N κ+1 − slightly wrong due to measurements that are, in prac- |φ(cid:105)−|ψ(cid:105) = |ecNm−κ+1(cid:105) ≤ |ei(cid:105) ≤N(cid:15) (16) tciacne,enxpoiescytathnadtrtehsetrriecdteudcetdodfiennistietyprmecaitsriioxno.nInthdeeefidr,stwκe (cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13) (cid:88)i=1 (cid:13)(cid:13) (cid:13)(cid:13) where (cid:15) = max e . The overall error is at most the sites will actually be full-rank, though most of its prob- i | i(cid:105) sum of the individual errors on each step. In addition, ability mass will lie on a subspace of dimension at most (cid:13) (cid:13) D. So, each time we apply a disentangling operation Uˆ , each of the (cid:15)i is(cid:13)revea(cid:13)led during the tomographic proce- i dure because they correspond to the post-selection suc- wealsowanttotruncate thereducedstatetothedesired cessprobability. Thisprovidesadirectmethodtocertify subspace. Similarly, a faulty estimate of σˆ will result in the inferred state. a small probability mass that lies outside the estimated support. GivenanestimateddisentanglingunitaryUˆ ,anystate 1 B. Parent Hamiltonians φ can be expressed as | (cid:105) Let ψ beasin(10)andsuchthat M [s]M [s] =1 Uˆ φ = |0(cid:105)⊗|η1(cid:105)+|e1(cid:105) (11) for all|i(cid:105)= 1,...,N. This can alwayss bei achiieve†d by 1| (cid:105) 1+ e e subsuming qudits at the beginning a(cid:80)nd end of the chain 1 1 (cid:104) | (cid:105) intoquditswithhigherdimensionandsuccessivesingular (cid:112) valuedecompositions[9,10]. NowletN,k Nsuchthat where|e1(cid:105)issomesub-normalizederrorvectorsupported N/k N,andassumethattheMPSisinje∈ctive[10]such on the subspace orthogonal to H1cutoff. The unitary Uˆ1 that ∈for all j =k,...,N 2k the set is chosen to minimize the norm (cid:15)1 = e1 e1 of this error − (cid:104) | (cid:105) vector. It is possible to directly estimate the magnitude of the error (cid:15)1 by measuring the first qudit in the stan- Mj+1[s1]···Mj+k[sk] si =1,...,di (17) dard basis; the error is equal to the population of the (cid:26) (cid:12) (cid:27) (cid:12) non-zero states. spansCDj+1×Dj+k+1. Then ψ is(cid:12)theuniquegroundstate | (cid:105) In subsequent steps of the recursion, we are given a of state of the form N/k 2 − Hˆ = Pˆ , (18) 0 i η + ecm n Uˆi...Uˆ1|φ(cid:105)= | (cid:105)⊗1⊗+|eic(cid:105)m e|cmi (cid:105) (12) n(cid:88)=0 (cid:104) i | i (cid:105) where Pˆ is the projector onto the subspace orthogonal where ecm is the accumula(cid:112)ted error vector that lies in to the rannge of the mapping Γn : CDnk+2k+1×Dnk+1 the sub|spiac(cid:105)e orthogonal to cutoff = 0 i (Cd) N i. Cdnk+1···dnk+2k, → Hi | (cid:105)⊗ ⊗ ⊗ − Asafirststep, wecantruncatethiserrorvectorbymea- suringthefirstiparticlesinthestandardbasisandpost- Γn(X)= tr XMnk+1[snk+1] Mnk+2k[snk+2k] ··· selectontheall-zerooutcome. Thisoccurswithaproba- sn(cid:88).k..+,1, (cid:104) (cid:105) bility roughly 1 (cid:15)cm, and leaves the system in the state snk+2k − i 0 i η . We then repeat the steps leading to Eq. 11 s s . | (cid:105)⊗ ⊗| i(cid:105) ×| nk+1··· nk+2k(cid:105) with the post-selected state η . The resulting state will (19) i | (cid:105) 8 To get an efficiently computable lower bound the energy and therefore we have the lower bound ∆E 1 γ, ≥ − gap, we use where ∆E =max λ Hˆ(Hˆ λ) 0 . (20) γ = max γ . (24) − ≥ n,m (cid:26) (cid:12) (cid:27) 0≤n≤N m (cid:12) 1 n(cid:88)mk 2k We find (cid:12) ≤| − | ≤ Pˆ Pˆ +Pˆ Pˆ Hˆ2 =Hˆ + PˆnPˆm Hˆ + n m m n, Injectivity may fail to hold in certain singular cases. ≥ 2 n,m n,m The simplest example given by the family of GHZ-type n(cid:88)(cid:54)=m 1≤|n−(cid:88)m|k≤2k states 1 (0,...,0 +eiφ 1,...,1 ). Since any local re- (21) √2 | (cid:105) | (cid:105) whereweomittednon-negativesummands. Nowconsider duceddensitymatrixisindependentofφ,itisimpossible the following quantity, which will bound the individual to distinguish the members of that family based on local terms in the previous equation, information alone. Indeed, in this example, the ground state space of Hˆ will be two-dimensional, spanned by 0,...,0 and 1,...,1 . One may check that the gap γ =min λ Pˆ Pˆ +Pˆ Pˆ +λ(Pˆ +Pˆ ) 0 | (cid:105) | (cid:105) n,m n m m n n m ≥ analysis above continues to hold in the degenerate case (cid:26) (cid:12) (cid:27) (unlike the original in [9]), now certifying the overlap (cid:12) =min λ(cid:12)(Pˆ +Pˆ )2 (1 λ)(Pˆ +Pˆ ) between (cid:37)ˆ and the ground-state space. This fact alone n m n m ≥ − (cid:26) (cid:12) (cid:27) implies an exponential reduction in the number of un- (cid:12) known parameters. It is easy to see that the small re- =1 max(cid:12) λ (Pˆ +Pˆ )2 λ(Pˆ +Pˆ ) , − n m ≥ n m maininguncertaintyabout(cid:37)ˆcanbeliftedinourexample (cid:26) (cid:12)(cid:12) (cid:27) (22) by measuring the “string operator” σx⊗...⊗σx, which (cid:12) hasexpectationvaluecosφ. Usinge.g.theresultsof[38], where the maximum is given by the smallest non-zero the method of this particular example immediately gen- eigenvalue of Pˆ +Pˆ . Hence eralizes to any MPS with a two-fold degeneracy, such n m as the W state. Higher degeneracies may be treated by Hˆ2 Hˆ γ Pˆ (1 γ)Hˆ, (23) straight-forward, but more tedious, methods. n,m n ≥ − ≥ − n,m 1 n(cid:88)mk 2k ≤| − | ≤ [1] Vogel, K. and Risken, H. Determination of quasiproba- 299–332 (2009). bility distributions in terms of probability distributions [8] Paris, M. and R˘eha´˘cek, J., eds., Quantum State Estima- fortherotatedquadraturephase.Phys.Rev.A40,2847– tion, no.649inLect.NotesPhys.(Springer, Heidelberg, 2849 (1989). 2004). [2] Smithey,D.T.,Beck,M.,Raymer,M.G.andFaridani,A. [9] Fannes, M., Nachtergaele, B. and Werner, R.F. Finitely MeasurementoftheWignerdistributionandthedensity correlatedstatesonquantumspinchains.Comm.Math. matrix of a light mode using optical homodyne tomog- Phys. 144, 443–490 (1992). raphy: Application to squeezed states and the vacuum. [10] Perez-Garcia, D., Verstraete, F., Wolf, M.M and Cirac, Phys. Rev. Lett. 70, 1244–1247 (1993). J.I. Matrix product state representations. Quant. Inf. [3] Ha¨ffner, H., Ha¨nsel, W., Roos, C.F., Benhelm, J., Chek- Comp. 7, 401–430 (2007). al-kar, D., Chwalla, M., Ko¨rber, T., Rapol, U.D., Riebe, [11] Vidal, G. Entanglement Renormalization. Phys. Rev. M., Schmidt, P.O., Becher, C., Gu¨hne, O., Du¨r, W. and Lett. 99 220405 (2007). Blatt,R.Scalablemultiparticleentanglementoftrapped [12] Rizzi, M., Montangero, S. and Vidal, G. Simulation of ions. Nature 438, 643–646 (2005). time evolution with multiscale entanglement renormal- [4] Leibfried, D., Knill, E., Seidelin, S., Britton, J., ization ansatz. Phys. Rev. A 77, 052328 (2008). Blakestad, R.B., Chiaverini, J., Hume, D.B., Itano, [13] O¨stlund, S. and Rommer, S. Thermodynamic Limit of W.M., Jost, J.D., Langer, C., Ozeri, R., Reichle, R. and Density Matrix Renormalization. Phys. Rev. Lett. 75, Wineland, D.J. Creation of a six-atom ‘Schro¨dinger cat’ 3537–3540 (1995). state. Nature 438, 639–643 (2005). [14] Hastings, M.B. Solving gapped Hamiltonians locally. [5] James, D.F.V., Kwiat, P.G., Munro, W.J. and White, Phys. Rev. B 73, 085115 (2006). A.G. Measurement of qubits. Phys. Rev. A 64, 052312 [15] Hastings,M.B.Anarealawforone-dimensionalquantum (2001). systems. J. Stat. Mech. P08024 (2007). [6] Dunn,T.J.andWalmsley,I.A.andMukamel,S.Experi- [16] Bloch, I., Dalibard, J. and Zwerger, W., Many-Body mentalDeterminationoftheQuantum-MechanicalState Physics with Ultracold Gases, Rev. Mod. Phys. 80, 885 ofaMolecularVibrationalModeUsingFluorescenceTo- (2008). mography, Phys. Rev. Lett. 74, 884 (1995). [17] Schoen, C., Hammerer, K., Wolf, M.M., Cirac, J. I. and [7] Lvovsky,A.I.andRaymer,M.G.Continuous-variableop- Solano, E. Sequential Generation of Entangled Multi- tical quantum-state tomography. Rev. Mod. Phys. 81, qubit States. Phys. Rev. A 75, 032311 (2007). 9 [18] Vidal, G. Efficient Classical Simulation of Slightly En- [29] Schollwo¨ck, U. The density-matrix renormalization tangled Quantum Computations. Phys. Rev. Lett. 91, group. Rev. Mod. Phys. 77, 259–315 (2005). 147902 (2003). [30] Schuch, N. and Cirac, J.I. Matrix Product State and [19] Gilchrist, A., Langford, A. K., Nielsen, M. A. Distance mean field solutions for one-dimensional systems can be measures to compare real and ideal quantum processes, found efficiently. Phys. Rev. A 82, 012314 (2010). Phys. Rev. A 71, 062310 (2005). [31] Aharonov, D., Arad, I. and Irani, S. An Efficient Algo- [20] Briegel, H. J. and Raussendorf, R. Persistent rithm for approximating 1D Ground States. Phys. Rev. Entanglement in arrays of Interacting Particles. A 82, 012315 (2010). Phys. Rev. Lett. 86, 910–913 (2001). [32] Eisert, J., Cramer, M., and Plenio, M.B. Area laws for [21] Candes,E.J.andRecht,B.ExactMatrixCompletionvia the entanglement entropy - a review, Rev. Mod. Phys. Convex Optimization. arXiv:0805.4471 [cs.IT]. 82, 277 (2010). [22] Cai, J-F., Candes, E.J. and Shen, Z. A Singular [33] Bratteli, O. and Robinson, D.W. Operator Algebras and Value Thresholding Algorithm for Matrix Completion. Quantum Statistical Mechanics, Texts and Monographs arXiv:0810.3286 [math.OC]. in Physics Vol. 2 (Springer, New York) 1979. [23] Candes, E.J. and Wakin, M.B. An introduction to com- [34] Verstraete,F.andCirac,J.I.Renormalizationalgorithms pressive sampling. IEEE Sig. Proc. Mag. 25, 21–30 for Quantum-Many Body Systems in two and higher di- (2008). mensions. arXiv:cond-mat/0407066. [24] Kosut, R.L. Quantum Process Tomography via l -norm [35] de Beaudrap, N., Ohliger, M., Osborne, T.J. and Eisert, 1 Minimization. arXiv:0812.4323 [quant-ph]. J.Solvingfrustration-freespinsystems.arXiv:1005.3781 [25] Gross,D.,Liu,Y-K.,Flammia,S.T.,Becker,S.andEis- (2010). ert, J. Quantum state tomography via compressed sens- [36] Tagliacozzo, L., Evenbly, G. and Vidal, G. Simulation ing. arXiv:0909.3304 [quant-ph] of two-dimensional quantum systems using a tree tensor [26] Gross, D. Recovering low-rank matrices from few coeffi- network that exploits the entropic area law. Phys. Rev. cients in any basis. arXiv:0910.1879 [cs.IT]. B 80, 235127 (2009). [27] Shabani, A., Kosut, R.L. and Rabitz, H. Compressed [37] Evenbly, G. and Vidal, G. Algorithms for entanglement Quantum Process Tomography. arXiv:0910.5498 [quant- renormalization. Phys. Rev. B 79, 144108 (2009). ph]. [38] Walgate, J., Short, A., Hardy, L. and Vedral, V. Local [28] Shabani,A.,Mohseni,M.,Lloyd,S.,Kosut,R.L.andRa- Distinguishability of Multipartite Orthogonal Quantum bitz, H. Efficient estimation of nearly sparse many-body States. Phys. Rev. Lett 85, 4972–4975 (2000). quantum Hamiltonians. arXiv:1002.1330 [quant-ph].

ebook img

Efficient quantum state tomography PDF

0.79 MB·
by  Marcus Cramer
#additional_collections #journals #arxiv
Save to my drive
Quick download
Download
Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Efficient quantum state tomography

Efficient quantum state tomography Marcus Cramer and Martin B. Plenio Institut fu¨r Theoretische Physik, Albert-Einstein Allee 11, Universita¨t Ulm, 89069 Ulm, Germany Steven T. Flammia and Rolando Somma Perimeter Institute for Theoretical Physics, Waterloo, Ontario, N2L 2Y5 Canada David Gross Institute for Theoretical Physics, Leibniz University Hannover, 30167 Hannover, Germany Stephen D. Bartlett School of Physics, The University of Sydney, Sydney, New South Wales 2006, Australia 1 Olivier Landon-Cardinal and David Poulin 1 D´epartement de Physique, Universit´e de Sherbrooke, Sherbrooke, Qu´ebec, Canada 0 2 Yi-Kai Liu n Institute for Quantum Information, California Institute of Technology, Pasadena, CA, USA a J Quantumstatetomography[1],theabilitytodeducethestateofaquantumsystemfrommeasured 3 data,isthegoldstandardforverificationandbenchmarkingofquantumdevices. Ithasbeenrealized 2 in systems with few components [2–7], but for larger systems it becomes infeasible because the numberofquantummeasurementsandtheamountofcomputationrequiredtoprocessthemgrows ] exponentiallyinthesystemsize. Hereweshowthatwecandoexponentiallybetterthandirectstate h p tomography for a wide range of quantum states, in particular those that are well approximated by - a matrix product state ansatz. We present two schemes for tomography in 1-D quantum systems t and touch on generalizations. One scheme requires unitary operations on a constant number of n subsystems, while the other requires only local measurements together with more elaborate post- a u processing. Both schemes rely only on a linear number of experimental operations and classical q postprocessingthatispolynomialinthesystemsize. Afurtherstrengthofthemethodsisthatthe [ accuracy of the reconstructed states can be rigorously certified without any a priori assumptions. 1 v I. INTRODUCTION ofsamples. Assumingonewereabletocollectallthedata 6 from an informationally complete measurement, one is 6 left with the intractable computational task of inverting 3 One of the principal features distinguishing classical 4 themeasuredfrequenciestofindanestimateofthestate. from quantum many-body systems is that quantum sys- . However, the traditional representation of quantum 1 tems require exponentially many parameters in the sys- states is in a sense too general. Indeed, states which oc- 0 tem size to fully specify the state, compared to only lin- 1 cur in many practical situations are specified by a small early many for classical systems. Put to use construc- 1 number of parameters. An efficient description could be tively, the exponential complexity enables the construc- : a practical preparation scheme which outputs the state; v tion of information processing devices fundamentally su- or, in the case of thermodynamical equilibrium states, a i X perior to any classical device. At the same time, how- localHamiltonianandatemperature. Thisinsightisnot ever, this “curse of dimensionality” makes engineering r new: researchers in many-body physics and quantum in- a tasks—suchasverifyingthatthequantumprocessingde- formationtheoryhavefoundmanyclassesofstateswhich vice functions as intended—a daunting challenge. are described by a number of parameters scaling polyno- The full determination of the quantum state of a sys- mially in N [9–13] and which closely approximate the tem, known as quantum state tomography [1], has al- kind of states found in physical systems [14, 15]. How- ready been achieved by measuring a complete set of ob- ever, the question of whether these restricted classes can servables whose expectation values determine the quan- beputtouseinthecontextoftomographyhasremained tum state [2–7]. As it is typically formulated [8], simply largely open. to output an estimate for a generic state would take ex- In this work, we address the above challenge. The ponentialtimeinthesystemsizeN, giventhatthereare physical system we have in mind is one where the con- an exponential number of coefficients in a generic state’s stituents are arranged in a one-dimensional configura- description. Thisisbutoneofseveralinefficiencies. Most tion (e.g., ions in a linear trap [3]). But the methods quantum states have exponentially small amplitudes in thatwearepresentingherecanbegeneralizedtohigher- almosteverybasis,sotodistinguishanyoneofthoseam- dimensional arrangements such as those realized in opti- plitudesfromzero,onemusttakeanexponentialnumber cal lattices [16]. It is highly plausible that in such a set- 2 ting,correlationsbetweenneighboringparticlesaremuch more pronounced (due to direct interaction) than corre- lations between distant systems (mediated e.g. by global fluctuations of control fields). An efficiently describable classofstatesanticipatingexactlythisbehaviorhaslong beenstudiedunderthenamesoffinitelycorrelatedstates (FCS) or matrix product states (MPS) [9, 10]. Impor- tantly, restricting to this class is not a limitation since every statemaybewrittenasaMPSwithasuitable, al- beitpossiblylarge, matrixdimension. Sincemanystates that are relevant for quantum information processing or quantum many-body physics have a small (independent ofN)bonddimension, ourmethodsaredirectlyapplica- ble to such states; examples include, but are not limited to, groundandthermalstates, theGHZ,W,cluster, and AKLT states, the latter two being universal resources states for quantum computing. FIG. 1. Quantum circuit that transforms |φ(cid:105) into Given that standard tomography is no longer feasible |0(cid:105)⊗N−κ+1 ⊗|η(cid:105) with κ = 3. The unitaries Uˆ successively inarangeofrecentandupcomingexperimentsinvolving i disentangle the particles and the state |η(cid:105) on the last sites large numbers of qubits, our results represent a signifi- acts as a boundary condition to determine the MPS descrip- cant advance in the ability to verify and quantitatively tion of |φ(cid:105). and efficiently benchmark systems of experimental im- portance. σˆ tr [(cid:37)ˆ]. This reduced density matrix has the κ+1,...,N ≈ eigendecompositionσˆ = R σ φ φ wheretherank II. RESULTS r=1 r| r(cid:105)(cid:104) r| R dκ 1. Hence there exists a density matrix with one − ≤ (cid:80) fewerquditthathasthesamerankR andeigenvaluesσ r In the following we present two schemes for identify- asσˆ. Thereforewecandisentanglethefirstsiteinσˆ with ing systems that are well approximated by an MPS, ini- the following unitary acting on the first κ sites: tiallyfocusingonpurestatesforsimplicity. Wewillview each system as consisting of a linear chain of N qudits, d 1dκ−1 1 eachhavingdimensiond. Bothschemesrequirethemea- Uˆ = − − s s φ , (1) surement of linearly (in the system size N) many local | (cid:105)1⊗| (cid:48)(cid:105)2,...,κ(cid:104) sdκ−1+s(cid:48)+1|1,...,κ s=0 s(cid:48)=0 observables within finite accuracy, polynomial classical (cid:88) (cid:88) post-processing of the data and can certify the accuracy where φ ,..., φ have been extended in some arbi- 1 R | (cid:105) | (cid:105) of the reconstructed state without making any technical trary way to get a complete basis for sites 1,...,κ. Ap- assumptions about the state in the laboratory. The first plyingUˆ producesthestateUˆ φ = 0 v ,where 1 2,...,N | (cid:105) | (cid:105) ⊗| (cid:105) scheme requires unitary control and local measurements v is some pure state on sites 2,...,N. Hence Uˆ disen- while the second scheme removes the need for unitary |ta(cid:105)nglesthefirstquditfromalltheothers. Now,setaside control at the cost of more elaborate post-processing. this first qudit, look at sites 2,...,κ+1, and repeat the aboveprocessasindicatedonFig.1. Inthisway,oneob- tainsasequenceofunitariesUˆ ,...,Uˆ ,whereeach 1 N κ+1 A. Scheme based on unitary transformations Uˆ actsonsitesi,...,i+κ 1. Thisseq−uencetransforms i φ into Uˆ Uˆ φ −= 0 N κ+1 η , where η N κ+1 1 ⊗ − The key idea of the method consists of a sequential i|s(cid:105)some pure−stat·e·o·n t|he(cid:105)last| κ(cid:105) 1 sites⊗. | (cid:105) | (cid:105) − procedure to disentangle the left hand side of the chain In summary, this scheme infers the quantum circuit from the right hand side, using a sequence of unitary usedtoprepareanMPS[17]. TheMPSdecompositionof operations with small interaction length independent of φ canthenbeobtainedreadilyfromtheU and η [18]. i | (cid:105) | (cid:105) N. The result will be a product state and a sequence If the state in the laboratory (cid:37)ˆ is arbitrary, then the of local unitary operations from which to construct the reduced density matrices σˆ will generally have full rank. original state. Hence in each step we will need to truncate the κ qudit Supposetheidealstateinthelaboratoryis(cid:37)ˆ= φ φ, state σˆ to a rank R subspace with R < dκ 1. Then the − | (cid:105)(cid:104) | which we assume for clarity is a MPS of given bond di- above method will produce an MPS approximation to (cid:37)ˆ. mension. This implies that the rank of reductions to The accuracy of this estimate can be certified, without one part of a bipartite (left vs. right) split of the chain any assumptions on the state, by keeping track of the is bounded by a constant R. The protocol starts by effects of truncating each of the reduced states σˆ. As estimating, through standard state tomography, the re- shownintheMethods,errorsofmagnitude(cid:15)duetofinite duced density matrix of the first κ= log (R) +1 sites, measurement precision or truncation error (as measured (cid:100) d (cid:101) 3 bytheweightofthetruncatedspace)accumulateatmost closetotheσˆ . A priori itisunclearwhethersuchacon- i linearly with the number of sites, and can be evaluated venient witness always exists and how it could be found directlyfromthedata,leadingtoanestimateofaccuracy efficiently. However,usingformalmethods,onecanshow N(cid:15). that if the true state (cid:37)ˆ is close to a generic MPS, then Thepresentschemerequiresunitarycontrolofκneigh- such a witness Hamiltonian always exists [10]. What is boringqudits,whichischallengingtoimplementinmany more,itcanbeconstructedfromtheestimateofthealgo- current experimental settings. We now present a second rithm sketched below. Its properties, chief among them scheme that avoids unitary control and requires only lo- the gap, are efficiently computable. In the Methods sec- cal measurements. tion, we detail the efficient computation of these quan- tities, and we also consider how to treat states such as the GHZ for which local marginals alone are not quite B. Scheme based on local measurements: sufficient for complete characterization (they violate our Certification of estimated state “generic” condition). Consider again the state (cid:37)ˆin the laboratory and sup- pose that a tomographically-complete set of local mea- surements on all groups of k neighbouring qubits has C. An illustrative example beenperformed. Furthersupposethatsufficientdatahas been taken to yield estimates σˆ of the local reductions i (cid:37)ˆi =tr1,...,i;i+k+1,...,N[(cid:37)ˆ] such that We illustrate how our certification procedure operates if our estimate for the state (cid:37)ˆ is a linear cluster state (cid:37)ˆ σˆ (cid:15) . (2) i i tr i [20]. Theclusterstateisdefinedastheuniqueeigenstate (cid:107) − (cid:107) ≤ (with eigenvalue +1) of stabilizers Kˆ = Zˆ Xˆ Zˆ Determining these approximate reduced density opera- i i 1 i i+1 for all i = 2,...,N 1 (together with bounda−ry terms tors σˆi completes the experimental work. In the remain- Xˆ Zˆ andZˆ Xˆ ,−whichwedonottreatseparatelyfor derwedescribetheclassicalpost-processingthatwillre- 1 2 N 1 N simplicity). A−ssume that we have performed standard sultinaMPSestimate ψ to(cid:37)ˆandalowerboundtothe | (cid:105) quantum state tomography on sets of three neighbour- fidelity ψ (cid:37)ˆψ [19]thatdoesnotrequireassumptionson (cid:104) | | (cid:105) ing spins, k =3, which is the smallest useful set because the nature of the state (cid:37)ˆ. in a cluster state the rank of the reduced density ma- We start with the latter, since the following easy trices of contiguous blocks is upper bounded by R = 4. calculation yields the fidelity bound we have in mind Let us now assume that on the basis of these data, our and hints at the MPS estimate we are after. Suppose, procedure suggests that the linear cluster state is indeed for the sake of the argument, that ψ is the unique | (cid:105) our estimate. The local Hamiltonian in this case is given ground state (with energy zero) of a local Hamiltonian Hiˆng=onlyiohˆni,siwtehserie+t1h,e..hˆ.i,iis+akp(raosjeitcttiuornnsopoeurta,tgoernaecritc- bpyroHjˆect=ors,iHˆ(1h−asKˆtih)e/2c,luwstheerresttahtee (a1s −itsKˆuin)i/q2ue=ghˆroiuanrde (cid:80) MPSa(cid:80)reofthistype). Then,expandingintheeigenbasis state(withenergyzero)andanenergygap∆E =1. The Hˆ = 2nN=−01En|En(cid:105)(cid:104)En|, fibdouelnitdyedbebtyweeψnth(cid:37)eˆcψluster=st1ate|ψC(Str(cid:105)[hˆanσˆd]t+he(cid:15)s)t,atweh(cid:37)ˆeries (cid:104) CS| | CS(cid:105) − i i i i tr[(cid:80)Hˆ(cid:37)ˆ]≥∆E (cid:104)En|(cid:37)ˆ|En(cid:105)=∆E(1−(cid:104)ψ|(cid:37)ˆ|ψ(cid:105)), (3) t(cid:15)ailfreormrorEinq.t(h3e)loqcuaalnetxifipeesritmheensttaa(cid:80)ltiessttiicmalataensd,aenxdpetrri[mhˆeσˆn-] i i n>0 (cid:88) quantifieshowmuchthelaboratorystate(cid:37)ˆdeviatesfrom where we denoted by ∆E the energy gap above the an exact cluster state. ground state ψ . Hence, we have the fidelity bound Tomography on a cluster state can also be performed | (cid:105) with the scheme based on unitary transformations. A tr[h ρˆ] 1 ψ (cid:37)ˆψ 1 i i 1 tr[hˆ σˆ ]+(cid:15) . cluster state is the output of a quantum circuit where i i i (cid:104) | | (cid:105)≥ − ∆E ≥ − ∆E each qubit is initially prepared in the state + = (cid:80) (cid:16)(cid:88)i ((cid:17)4) 1/√2 0 + 1 and a controlled phase transform| a(cid:105)tion | (cid:105) | (cid:105) CZ acts successfully on each pair of neighboring qubits. In other words, the Hamiltonian acts as a witness for its The C(cid:0)Z gate (cid:1)changes the sign of state 11 and acts | (cid:105) ground state ψ . This bound is tight: suppose the ex- trivially on the other states of the computational basis. | (cid:105) perimental estimates σˆi and the reductions of the state Thus, a cluster state is the output of a circuit whose in the laboratory (cid:37)ˆi coincide, that is (cid:15)i = 0. If, in addi- structurecorrespondstotheoneindicatedonFig.1with tion, the reductions of ψ match the σˆi then, as ψ was κ = 2 and the scheme based on unitary transformations | (cid:105) | (cid:105) assumed to be the unique ground state with energy zero directly applies. Note that the unitary scheme takes ad- of hˆ , we have tr[hˆ σˆ ]=0, i.e., ψ (cid:37)ˆψ =1. vantageofthedecreasedrankofareduceddensitymatrix i i i i i (cid:104) | | (cid:105) The goal is now clear: find a local gapped Hamilto- on the boundary to save one qubit worth of local tomo- nia(cid:80)n Hˆ such that (cid:80)the reductions of its ground state are graphic effort (κ=2 vs. k =3). 4 D. Scheme based on local measurements: Efficient 1 determination of an MPS estimate 700 1−fN,n With the experimentally obtained σˆ , we now turn to i the task of finding an MPS ψ such that its reductions | (cid:105) 500 tr [ψ ψ ] closely match the σˆ . In other 1,...,i;i+k+1,...,N i | (cid:105)(cid:104) | words: Let Pˆi,k be all possible products of Pauli oper- m ators (enumerated by m) that act non-trivially only on 300 sites i+1,...,i+k. Then, as the Pˆi are an orthogonal m basis, the σˆ may be expanded as i σˆi = 21N tr[σˆiPˆmi ]Pˆmi , (5) 100 1 812 m 1 102 1 (cid:88) 400 300 1 122 N2 where the expectations tr[σˆPˆmi ] ∈ R are obtained as re- n 200 100 3102162 sults of tomographic measurements. Then we need to find a matrix ψ ψ such that for all m and i the ex- FIG. 2. Performance of the MPS-SVT algorithm for the pectations tr[ψ| (cid:105)ψ(cid:104) Pˆ|i ] coincide with those of the tomo- groundstate(thetargetstate|φ(cid:105))ofthecriticalIsingmodel. | (cid:105)(cid:104) | m We chose k = 2, i.e., only nearest neighbour reductions are graphic estimates, tr[ψ ψ Pˆi ]=tr[σˆ Pˆi ]. | (cid:105)(cid:104) | m i m used to reconstruct the state. Plot illustrates the scaling of The method of choice for such a problem is singular theerrorinthefidelity1−f =1−|(cid:104)φ|y (cid:105)|2 ∼N2/nwith N,n n value thresholding (SVT) [21, 22], which has been devel- the number of spins N and the iterations n of the algorithm. oped very recently in the context of classical compres- sive sampling or matrix completion [23] and may also be applied to the quantum setting [24–28]. SVT is a re- These numerical examples suggest convergence of our cursive algorithm that provably converges to a low-rank algorithmtoaMPSthatcloselymatchestheexperimen- matrix satisfying constraints of the type tr[|ψ(cid:105)(cid:104)ψ|Pˆmi ] = tally obtained reductions σˆi. To arrive at the fidelity tr[σˆiPˆmi ]. Unfortunately,astraightforwardapplicationof bound we follow the steps of Section IIB: (i) Obtain es- SVT requires time and memory that scale exponentially timates σˆ of the reductions to k adjacent spins (cid:37)ˆ of the i i withthenumberofparticles. However, amodificationof state in the laboratory such that σˆ (cid:37)ˆ (cid:15) , (ii) i i tr i (cid:107) − (cid:107) ≤ the algorithm allows us to overcome this problem. compute the expectations p =tr[σˆ Pˆi ], which are the Giventhemeasuredvaluestr[σˆiPˆmi ]thealgorithmmay input to the MPS-SVT algomriithm, (iiii)mobtain a MPS es- then be described as follows. First set up the operator timate y , the reductions of which closely match the Rˆ = m,itr[σˆiPˆmi ]Pˆmi /2N andinitializeYˆ0 tosomearbi- σˆi by u|tilniz(cid:105)ing the MPS-SVT algorithm. As yn is an | (cid:105) trarymatrix(e.g.,thezeromatrix). Thenproceedrecur- MPS, one can then efficiently obtain a parent Hamilto- (cid:80) sively by finding the eigenstate yn with largest eigen- nian [10]andalowerbound,∆,ontheenergygapabove | (cid:105) value, y , of Yˆ and set the ground state (see Methods for details). Putting all n n this together, the above programme returns a state y , Xˆn =yn (cid:104)yn|P2ˆNmi |yn(cid:105)Pˆmi , (6) itthsaptarentHamiltonianHˆ = ihˆi,andanumber∆|sunc(cid:105)h (cid:88)m,i (cid:80) Yˆn+1 =Yˆn+δn(Rˆ−Xˆn). y (cid:37)ˆy 1 i((cid:15)i+tr[hˆiσˆi]). (7) n n Sofar,thisalgorithmstillsuffersfromthefactthatinev- (cid:104) | | (cid:105)≥ − ∆ (cid:80) erystepthe2N 2N matrixYˆ needstobediagonalized. n However, theYˆ×areoftheform M a Pˆi , a R, n m,i m,i m m,i ∈ wherethePˆi actnon-triviallyonlyonsitesi+1,...,i+k, m (cid:80) i.e., theyhavetheformofalocal“Hamiltonian”. Hence, E. Example: Strongly interacting quantum systems y can be determined as the highest energy state of n | (cid:105) this Hamiltonian. For this task standard methods have Westartwithgroundstatesofnearest-neighborHamil- been developed in condensed matter physics [13, 29] for tonians on a chain, i.e., the φ = gs are completely de- | (cid:105) | (cid:105) which the number of parameters scale polynomially in termined by all the reductions to two adjacent spins and the system size and converge rapidly [30, 31] to the op- weexpecttheabovealgorithmnotonlytoproducestates timal MPS approximation. The standard but exponen- that match the reduced density matrices of the ground tially inefficient SVT algorithm possesses a convergence statesbut,infact,statesthatarethemselvesclosetothe proof while our efficient modification does not. Hence, ground states. Among ground states of one-dimensional we now present numerical examples for different target nearest-neighbor Hamiltonians, those at a critical point states φ to demonstrate the feasibility and efficiency of arethemostchallengingtoapproximatebyMPSasthey | (cid:105) the proposed algorithm. violate the entanglement area law [32]. We demonstrate 5 determine the ground state gs (our target state φ ) | (cid:105) | (cid:105) and its reductions and then computed the fidelity f N,n 1 fN,n after n iterations of the MPS-SVT algorithm, see Fig. 3. − ￿ F. Example: W-state preparation in ion traps 0.2 Ourmethodisofinterestformanysituationsinwhich standard tomography will not be feasible. This is the case for the verification of state preparation in experi- mentswithtoomanyparticles. Anexampleistherecent 0.1 ion trap experiment [3] for the preparation of W-states, φ = (10 0 + 010 0 + + 0 01 )/√N, that | (cid:105) | ··· (cid:105) | ··· (cid:105) ··· | ··· (cid:105) were limited to 8 qubits principally because the classi- cal postprocessing of data became prohibitive for longer chains. Here we demonstrate the efficiency of our ap- 15 20 25 30 N proach (we are not limited to few ions and demonstrate convergence for up to 20 ions – even higher number of ions are easily accessible due to the MPS alteration of theSVTmethod)byillustratinghowonewouldpostpro- FIG. 3. Fidelity fN,n =|(cid:104)φ|yn(cid:105)|2, for a fixed value n=5, as cessexperimentallyobtainedreduceddensitymatricesto afunctionofthenumberofspinsN forthegroundstate(the guaranteethegenerationof φ orastateveryclosetoit. targetstate|φ(cid:105))oftherandomnearest-neighbourHamiltoni- | (cid:105) Notethat,asintheabovespinchainexamples,oneneed ans of Eq. 8. As in Fig. 2, we chose k=2 to reconstruct the only take tomographic data on pairs (k = 2) of neigh- state. The plot shows densities (arrows indicate the mean) bouring qubits. We mimic experimental noise by adding obtained from 1000 random realizations. Similar to the Ising model,thescalingforfixednof1−f isbetterthan∼N2. Gaussian distributed random numbers with zero mean N,n to the p . After initializing the algorithm with Yˆ =Rˆ, mi 0 where we obtain Rˆ from the MPS representation of φ , | (cid:105) the effectiveness of our algorithm for such an example: weusex := p y Pˆi,k y asafigureofmerit the critical Ising model in a transverse field on a chain for convenrgence,mii.e|.,ma,if−te(cid:104)r an|gimven| nn(cid:105)u|mber of iterations, oflengthN withopenboundaryconditions. Theground we pick the y(cid:80) with minimum x . The result of such a n n state of this Hamiltonian is unique and hence it is com- procedure is|sh(cid:105)own in Fig. 4. pletely characterized by its reductions to k = 2 neigh- bouringsites. Inotherwords,ifwefindanMPSthathas thesamereductions,thefidelitywillbeone. Weproceed III. DISCUSSION as follows. (i) We obtain the reductions (cid:37)ˆ to two neigh- i bouring sites of the true ground state, (ii) from these Wehavepresentedtwoschemesthatefficientlyproduce reductions we obtain the expectations pmi = tr[(cid:37)ˆiPˆmi], anMPSdescriptionasatomographicestimateofaquan- whicharetheinputtotheMPS-SVTalgorithm. InFig.2 tum state, along with a tight fidelity bound. We empha- we show the fidelity fN,n = yn φ 2 of the true ground size that no assumptions are necessary for our scheme; if |(cid:104) | (cid:105)| state φ and the n’th iterate of the above algorithm as nosuchMPSdescriptionexists,thiswillbeevidentfrom | (cid:105) a function of n and the length N of the chain. It shows the local tomographic data and our schemes will herald that for fixed system size 1 fN,n decreases as 1/n a failure. However, the enormous successes of MPS for − ∼ while for fixed n it increases slower than N2. This pro- describingbothone-dimensionalquantumsystemsfound vides an indication that our algorithm is polynomial in in nature as well as a host of states relevant to quantum the system size. informationensuresthatourmethodswillbeveryuseful The Ising model is solvable and, in order to show that in practice. we are not considering a special case that is particu- Sofarwepresentedthemethodforpurestatesandone- larly favourable, we also consider one-dimensional ran- dimensional systems. Various generalizations are pos- dom Hamiltonians of the form sible: Our first scheme using unitary control can also handle mixed states corresponding to small ensembles N 1 Hˆ = − rˆ(i)rˆ(i) , (8) of pure MPS. Suppose we are presented with a state (cid:37)ˆ i i+1 that is a mixture of M pure states, each of which is an i=1 (cid:88) MPS having bond dimension D. Then the reduction of where the rˆ(i), rˆ(i) act on spin i and i+1, respectively, (cid:37)ˆto any subsystem has rank at most MD. We can pro- i i+1 and are hermitian matrices with entries that have real ceed as before, performing unitary operations on blocks and imaginary part picked from a uniform distribution of κ = log (MD) +1 sites, in order to disentangle in- (cid:100) d (cid:101) over [ 1,1]. For each Hamiltonian, as before, we first dividual sites from the rest of the chain. At the end of − 6 fN,n tended to mixed states by considering purifications and can then, e.g., also handle thermal states of local Hamil- tonians,underthephysicallyreasonableassumptionthat theentropydensityexists[33]. Inaddition,itcanbegen- 0.98 eralized to all mixed finitely correlated states (FCS) [9], though it is not always possible to certify the resulting estimates. Higher-dimensional systems are more challenging, be- 0.96 cause the most straightforward generalization of MPS, known as projected entangled-pair states (PEPS) [34], cannot be computed as efficiently. However, the certifi- 0.94 cation method using a frustration-free parent Hamilto- nian remains efficient in the case of qubits with nearest- neighbor couplings [35]. Combinations of our techniques can be used to reconstruct other classes of states, such 0.92 as tree tensor networks [36] and multiscale entanglement 10 15 20 N renormalizationansatz(MERA)states[37],forwhichef- ficient heuristics for minimizing local Hamiltonians are FIG. 4. Performance of the MPS-SVT algorithm√for W- available. states,|φ(cid:105)=(|10···0(cid:105)+|010···0(cid:105)+···+|0···01(cid:105))/ N. We are not limited to few ions and demonstrate convergence for up to 20 ions – even higher number of ions are easily acces- ACKNOWLEDGMENTS sible due to the MPS alteration of the SVT method, demon- stratingtheefficiencyofourapproach. Wemimicexperimen- tal noise by adding Gaussian distributed random numbers The authors acknowledge discussion with F.G.S.L. withzeromeantothelocalexpectationsp =tr[σˆ Pˆ ]and Brand˜ao at early stages of this project. The work at mi i mi show results for n = 4000 MPS-SVT iterations. Plot shows UlmUniversityhasbeensupportedbytheEUIntegrated fN,n =|(cid:104)φ|yn(cid:105)|2asafunctionofthenumberofions,N,forno Project QAP, the EU STREP’s CORNER and HIP and noise (dots) and Gaussian noise (densities obtained from 100 an Alexander von Humboldt Professorship. SDB ac- realizations for each N, arrows indicate mean) with a stan- knowledgesthesupportoftheAustralianResearchCoun- dard deviation of 0.005 (blue; only even values of N plotted cil and the Perimeter Institute. STF and RS were sup- for clarity) and 0.01 (black, odd N). portedbythePerimeterInstituteforTheoreticalPhysics. ResearchatPerimeterissupportedbytheGovernmentof CanadathroughIndustryCanadaandbytheProvinceof the chain, we will find a mixed state η of rank M on the Ontario through the Ministry of Research & Innovation. lastκ 1sites. Wedecomposeη asamixtureofM pure − DG is glad to acknowledge support from the EU (COR- states. Thisyieldsarepresentationof(cid:37)ˆasanensembleof NER).OLCandDParepartiallyfundedbyNSERCand M pure MPS, each with bond dimension at most dMD. FQRNT. YKL is funded by the US ARO/NSA. Our second scheme using local measurements can also beextendedtohandlemixedstates. Whilethek-particle reduced density matrices do not uniquely determine the IV. METHODS mixed state (cid:37)ˆ, reconstructions of better and better qual- ity can be obtained by increasing k. As an example, suppose (cid:37)ˆ is the Gibbs state corresponding to a k-local WestartbyrecallingtheMPSrepresentationofastate HamiltonianHˆ, i.e. thestateminimizingthefreeenergy ψ withopenboundaryconditions(generalisationstope- | (cid:105) riodic boundary conditions are entirely straightforward). tr[(cid:37)ˆHˆ] TS((cid:37)ˆ). (9) − d1−1 dN−1 The first term is, as before, determined by the reduced ψ = M1[s1] MN[sN]s1 sN , (10) | (cid:105) ··· ··· | ··· (cid:105) density matrices. The entropy of the total state how- s(cid:88)1=0 s(cid:88)N=0 ever can only be learned exactly from the complete den- where the M [s] are D D matrices with D = sity matrix. Yet, for essentially all reasonable physical i i i+1 1 × D = 1. We denote the bond dimension by D = systems, the entropy density lim S(tr ((cid:37)ˆ))/k in N+1 k k+1,... the thermal state of a Hamiltonia→n∞exists [33] (In partic- maxDi. ular, finitely correlated states are precisely those states whoseentropydensityisexactlyequaltoS(tr ((cid:37)ˆ)) k+1,... S(tr ((cid:37)ˆ))forsomefinitevalueofk). Asaconsequenc−e, A. Direct tomography k,... thetotalentropyofthestatecanbeestimatedefficiently from knowledge of the reduced density matrices. Hence, This method proceeds by disentangling all the qudits our second scheme using local measurements may be ex- of the chain sequentially. Thus, it yields a valid MPS 7 description if every unitary exactly disentangles one qu- be dit. Put another way, while it is crucial to obtain a good estimate of the dκ−1-dimensional subspace on which σˆ is Uˆ Uˆ ...Uˆ φ = |0(cid:105)⊗i⊗Uˆi+1|ηi(cid:105)+Uˆi+1|ecim(cid:105) (13) i+1 i 1 supported,itisnotnecessary toidentifytheeigenvectors | (cid:105) 1+ ecm ecm (cid:104) i | i (cid:105) of σˆ exactly : any set of orthonormal vectors generating 0 i+1 η + ecm the subspace is sufficient for our tomography procedure = | (cid:105)⊗ (cid:112)⊗| i+1(cid:105) | i+1(cid:105) (14) and leads to an MPS description in another gauge [10]. 1+ ecm ecm (cid:104) i+1| i+1(cid:105) This property will be central to our error analysis. (cid:113) Tounderstandtheeffectoferrorsandimperfectionsin where our tomography procedure, consider the very first step e +U ecm of the recursive procedure. Tomography is performed on ecm = | i(cid:105) i+1| i (cid:105) (15) | i+1(cid:105) 1+ ecm ecm the first κ sites to ideally find a state with non-maximal (cid:104) i | i (cid:105) support, and unitary Uˆ1 is applied to rotate that state and therefore (cid:15)cm (cid:15)cm(cid:112)+(cid:15) . into the subspace cutoff = 0 (Cd) n 1. In any ex- i+1 ≤ i i+1 H1 | (cid:105)⊗ ⊗ − Thus, we see that errors accumulate linearly with perimentalsetting,theresultingstateUˆ1 φ wouldsurely the number of particles; if we denote ψ = ncaoutsleietheentsitraetlyeoinftthheatsyssutbemspaiscen.otTehxisaccta|lyn(cid:105)abneMeitPhSerwbiteh- hUˆa1†v.e..UˆN†−κ+1|0(cid:105)N−κ+1|ηN−κ+1(cid:105)theestimatedM|P(cid:105)S,we bond dimension D, but merely close to one or because our estimate of the density matrix σˆ on sites 1 to κ is N κ+1 − slightly wrong due to measurements that are, in prac- |φ(cid:105)−|ψ(cid:105) = |ecNm−κ+1(cid:105) ≤ |ei(cid:105) ≤N(cid:15) (16) tciacne,enxpoiescytathnadtrtehsetrriecdteudcetdodfiennistietyprmecaitsriioxno.nInthdeeefidr,stwκe (cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13) (cid:88)i=1 (cid:13)(cid:13) (cid:13)(cid:13) where (cid:15) = max e . The overall error is at most the sites will actually be full-rank, though most of its prob- i | i(cid:105) sum of the individual errors on each step. In addition, ability mass will lie on a subspace of dimension at most (cid:13) (cid:13) D. So, each time we apply a disentangling operation Uˆ , each of the (cid:15)i is(cid:13)revea(cid:13)led during the tomographic proce- i dure because they correspond to the post-selection suc- wealsowanttotruncate thereducedstatetothedesired cessprobability. Thisprovidesadirectmethodtocertify subspace. Similarly, a faulty estimate of σˆ will result in the inferred state. a small probability mass that lies outside the estimated support. GivenanestimateddisentanglingunitaryUˆ ,anystate 1 B. Parent Hamiltonians φ can be expressed as | (cid:105) Let ψ beasin(10)andsuchthat M [s]M [s] =1 Uˆ φ = |0(cid:105)⊗|η1(cid:105)+|e1(cid:105) (11) for all|i(cid:105)= 1,...,N. This can alwayss bei achiieve†d by 1| (cid:105) 1+ e e subsuming qudits at the beginning a(cid:80)nd end of the chain 1 1 (cid:104) | (cid:105) intoquditswithhigherdimensionandsuccessivesingular (cid:112) valuedecompositions[9,10]. NowletN,k Nsuchthat where|e1(cid:105)issomesub-normalizederrorvectorsupported N/k N,andassumethattheMPSisinje∈ctive[10]such on the subspace orthogonal to H1cutoff. The unitary Uˆ1 that ∈for all j =k,...,N 2k the set is chosen to minimize the norm (cid:15)1 = e1 e1 of this error − (cid:104) | (cid:105) vector. It is possible to directly estimate the magnitude of the error (cid:15)1 by measuring the first qudit in the stan- Mj+1[s1]···Mj+k[sk] si =1,...,di (17) dard basis; the error is equal to the population of the (cid:26) (cid:12) (cid:27) (cid:12) non-zero states. spansCDj+1×Dj+k+1. Then ψ is(cid:12)theuniquegroundstate | (cid:105) In subsequent steps of the recursion, we are given a of state of the form N/k 2 − Hˆ = Pˆ , (18) 0 i η + ecm n Uˆi...Uˆ1|φ(cid:105)= | (cid:105)⊗1⊗+|eic(cid:105)m e|cmi (cid:105) (12) n(cid:88)=0 (cid:104) i | i (cid:105) where Pˆ is the projector onto the subspace orthogonal where ecm is the accumula(cid:112)ted error vector that lies in to the rannge of the mapping Γn : CDnk+2k+1×Dnk+1 the sub|spiac(cid:105)e orthogonal to cutoff = 0 i (Cd) N i. Cdnk+1···dnk+2k, → Hi | (cid:105)⊗ ⊗ ⊗ − Asafirststep, wecantruncatethiserrorvectorbymea- suringthefirstiparticlesinthestandardbasisandpost- Γn(X)= tr XMnk+1[snk+1] Mnk+2k[snk+2k] ··· selectontheall-zerooutcome. Thisoccurswithaproba- sn(cid:88).k..+,1, (cid:104) (cid:105) bility roughly 1 (cid:15)cm, and leaves the system in the state snk+2k − i 0 i η . We then repeat the steps leading to Eq. 11 s s . | (cid:105)⊗ ⊗| i(cid:105) ×| nk+1··· nk+2k(cid:105) with the post-selected state η . The resulting state will (19) i | (cid:105) 8 To get an efficiently computable lower bound the energy and therefore we have the lower bound ∆E 1 γ, ≥ − gap, we use where ∆E =max λ Hˆ(Hˆ λ) 0 . (20) γ = max γ . (24) − ≥ n,m (cid:26) (cid:12) (cid:27) 0≤n≤N m (cid:12) 1 n(cid:88)mk 2k We find (cid:12) ≤| − | ≤ Pˆ Pˆ +Pˆ Pˆ Hˆ2 =Hˆ + PˆnPˆm Hˆ + n m m n, Injectivity may fail to hold in certain singular cases. ≥ 2 n,m n,m The simplest example given by the family of GHZ-type n(cid:88)(cid:54)=m 1≤|n−(cid:88)m|k≤2k states 1 (0,...,0 +eiφ 1,...,1 ). Since any local re- (21) √2 | (cid:105) | (cid:105) whereweomittednon-negativesummands. Nowconsider duceddensitymatrixisindependentofφ,itisimpossible the following quantity, which will bound the individual to distinguish the members of that family based on local terms in the previous equation, information alone. Indeed, in this example, the ground state space of Hˆ will be two-dimensional, spanned by 0,...,0 and 1,...,1 . One may check that the gap γ =min λ Pˆ Pˆ +Pˆ Pˆ +λ(Pˆ +Pˆ ) 0 | (cid:105) | (cid:105) n,m n m m n n m ≥ analysis above continues to hold in the degenerate case (cid:26) (cid:12) (cid:27) (unlike the original in [9]), now certifying the overlap (cid:12) =min λ(cid:12)(Pˆ +Pˆ )2 (1 λ)(Pˆ +Pˆ ) between (cid:37)ˆ and the ground-state space. This fact alone n m n m ≥ − (cid:26) (cid:12) (cid:27) implies an exponential reduction in the number of un- (cid:12) known parameters. It is easy to see that the small re- =1 max(cid:12) λ (Pˆ +Pˆ )2 λ(Pˆ +Pˆ ) , − n m ≥ n m maininguncertaintyabout(cid:37)ˆcanbeliftedinourexample (cid:26) (cid:12)(cid:12) (cid:27) (22) by measuring the “string operator” σx⊗...⊗σx, which (cid:12) hasexpectationvaluecosφ. Usinge.g.theresultsof[38], where the maximum is given by the smallest non-zero the method of this particular example immediately gen- eigenvalue of Pˆ +Pˆ . Hence eralizes to any MPS with a two-fold degeneracy, such n m as the W state. Higher degeneracies may be treated by Hˆ2 Hˆ γ Pˆ (1 γ)Hˆ, (23) straight-forward, but more tedious, methods. n,m n ≥ − ≥ − n,m 1 n(cid:88)mk 2k ≤| − | ≤ [1] Vogel, K. and Risken, H. Determination of quasiproba- 299–332 (2009). bility distributions in terms of probability distributions [8] Paris, M. and R˘eha´˘cek, J., eds., Quantum State Estima- fortherotatedquadraturephase.Phys.Rev.A40,2847– tion, no.649inLect.NotesPhys.(Springer, Heidelberg, 2849 (1989). 2004). [2] Smithey,D.T.,Beck,M.,Raymer,M.G.andFaridani,A. [9] Fannes, M., Nachtergaele, B. and Werner, R.F. Finitely MeasurementoftheWignerdistributionandthedensity correlatedstatesonquantumspinchains.Comm.Math. matrix of a light mode using optical homodyne tomog- Phys. 144, 443–490 (1992). raphy: Application to squeezed states and the vacuum. [10] Perez-Garcia, D., Verstraete, F., Wolf, M.M and Cirac, Phys. Rev. Lett. 70, 1244–1247 (1993). J.I. Matrix product state representations. Quant. Inf. [3] Ha¨ffner, H., Ha¨nsel, W., Roos, C.F., Benhelm, J., Chek- Comp. 7, 401–430 (2007). al-kar, D., Chwalla, M., Ko¨rber, T., Rapol, U.D., Riebe, [11] Vidal, G. Entanglement Renormalization. Phys. Rev. M., Schmidt, P.O., Becher, C., Gu¨hne, O., Du¨r, W. and Lett. 99 220405 (2007). Blatt,R.Scalablemultiparticleentanglementoftrapped [12] Rizzi, M., Montangero, S. and Vidal, G. Simulation of ions. Nature 438, 643–646 (2005). time evolution with multiscale entanglement renormal- [4] Leibfried, D., Knill, E., Seidelin, S., Britton, J., ization ansatz. Phys. Rev. A 77, 052328 (2008). Blakestad, R.B., Chiaverini, J., Hume, D.B., Itano, [13] O¨stlund, S. and Rommer, S. Thermodynamic Limit of W.M., Jost, J.D., Langer, C., Ozeri, R., Reichle, R. and Density Matrix Renormalization. Phys. Rev. Lett. 75, Wineland, D.J. Creation of a six-atom ‘Schro¨dinger cat’ 3537–3540 (1995). state. Nature 438, 639–643 (2005). [14] Hastings, M.B. Solving gapped Hamiltonians locally. [5] James, D.F.V., Kwiat, P.G., Munro, W.J. and White, Phys. Rev. B 73, 085115 (2006). A.G. Measurement of qubits. Phys. Rev. A 64, 052312 [15] Hastings,M.B.Anarealawforone-dimensionalquantum (2001). systems. J. Stat. Mech. P08024 (2007). [6] Dunn,T.J.andWalmsley,I.A.andMukamel,S.Experi- [16] Bloch, I., Dalibard, J. and Zwerger, W., Many-Body mentalDeterminationoftheQuantum-MechanicalState Physics with Ultracold Gases, Rev. Mod. Phys. 80, 885 ofaMolecularVibrationalModeUsingFluorescenceTo- (2008). mography, Phys. Rev. Lett. 74, 884 (1995). [17] Schoen, C., Hammerer, K., Wolf, M.M., Cirac, J. I. and [7] Lvovsky,A.I.andRaymer,M.G.Continuous-variableop- Solano, E. Sequential Generation of Entangled Multi- tical quantum-state tomography. Rev. Mod. Phys. 81, qubit States. Phys. Rev. A 75, 032311 (2007). 9 [18] Vidal, G. Efficient Classical Simulation of Slightly En- [29] Schollwo¨ck, U. The density-matrix renormalization tangled Quantum Computations. Phys. Rev. Lett. 91, group. Rev. Mod. Phys. 77, 259–315 (2005). 147902 (2003). [30] Schuch, N. and Cirac, J.I. Matrix Product State and [19] Gilchrist, A., Langford, A. K., Nielsen, M. A. Distance mean field solutions for one-dimensional systems can be measures to compare real and ideal quantum processes, found efficiently. Phys. Rev. A 82, 012314 (2010). Phys. Rev. A 71, 062310 (2005). [31] Aharonov, D., Arad, I. and Irani, S. An Efficient Algo- [20] Briegel, H. J. and Raussendorf, R. Persistent rithm for approximating 1D Ground States. Phys. Rev. Entanglement in arrays of Interacting Particles. A 82, 012315 (2010). Phys. Rev. Lett. 86, 910–913 (2001). [32] Eisert, J., Cramer, M., and Plenio, M.B. Area laws for [21] Candes,E.J.andRecht,B.ExactMatrixCompletionvia the entanglement entropy - a review, Rev. Mod. Phys. Convex Optimization. arXiv:0805.4471 [cs.IT]. 82, 277 (2010). [22] Cai, J-F., Candes, E.J. and Shen, Z. A Singular [33] Bratteli, O. and Robinson, D.W. Operator Algebras and Value Thresholding Algorithm for Matrix Completion. Quantum Statistical Mechanics, Texts and Monographs arXiv:0810.3286 [math.OC]. in Physics Vol. 2 (Springer, New York) 1979. [23] Candes, E.J. and Wakin, M.B. An introduction to com- [34] Verstraete,F.andCirac,J.I.Renormalizationalgorithms pressive sampling. IEEE Sig. Proc. Mag. 25, 21–30 for Quantum-Many Body Systems in two and higher di- (2008). mensions. arXiv:cond-mat/0407066. [24] Kosut, R.L. Quantum Process Tomography via l -norm [35] de Beaudrap, N., Ohliger, M., Osborne, T.J. and Eisert, 1 Minimization. arXiv:0812.4323 [quant-ph]. J.Solvingfrustration-freespinsystems.arXiv:1005.3781 [25] Gross,D.,Liu,Y-K.,Flammia,S.T.,Becker,S.andEis- (2010). ert, J. Quantum state tomography via compressed sens- [36] Tagliacozzo, L., Evenbly, G. and Vidal, G. Simulation ing. arXiv:0909.3304 [quant-ph] of two-dimensional quantum systems using a tree tensor [26] Gross, D. Recovering low-rank matrices from few coeffi- network that exploits the entropic area law. Phys. Rev. cients in any basis. arXiv:0910.1879 [cs.IT]. B 80, 235127 (2009). [27] Shabani, A., Kosut, R.L. and Rabitz, H. Compressed [37] Evenbly, G. and Vidal, G. Algorithms for entanglement Quantum Process Tomography. arXiv:0910.5498 [quant- renormalization. Phys. Rev. B 79, 144108 (2009). ph]. [38] Walgate, J., Short, A., Hardy, L. and Vedral, V. Local [28] Shabani,A.,Mohseni,M.,Lloyd,S.,Kosut,R.L.andRa- Distinguishability of Multipartite Orthogonal Quantum bitz, H. Efficient estimation of nearly sparse many-body States. Phys. Rev. Lett 85, 4972–4975 (2000). quantum Hamiltonians. arXiv:1002.1330 [quant-ph].

See more

The list of books you might like

Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.
DMCA & Copyright: Dear all, most of the website is community built, users are uploading hundred of books everyday, which makes really hard for us to identify copyrighted material, please contact us if you want any material removed.
Copyright @ PDFdrive.to, 2022 | We love our users