Fast quantum search driven by environmental engineering

Rui Zhang and Tian Chen

1 National Engineering Laboratory for Risk Perception and Prevention(NEL-RPP),CAEIT,Beijing 100041,China

2 Beijing Key Laboratory of Nanophotonics and Ultrafine Optoelectronic Systems,School of Physics,Beijing Institute of Technology,Beijing 100081,China

Abstract Studies have demonstrated that a joined complete graph is a typical mathematical model that can support a fast quantum search.In this paper,we study the implementation of joined complete graphs in atomic systems and realize a quantum search of runtimebased on this implementation with a success probability of 50%.Even though the practical systems inevitably interact with the surrounding environment,we reveal that a successful quantum search can be realized through delicately engineering the environment itself.We consider that our study will bring about a feasible way to realize quantum information processing including quantum algorithms in reality.

Keywords:quantum walk,quantum search algorithm,environmental engineering,non-Markovian

1.Introduction

Quantum algorithms are widely applied in quantum information processing,due to the exponential speedup effect compared to their classical counterparts[1–5].As a useful tool for implementing quantum algorithms,graphs have been investigated to support many quantum algorithms,such as quantum search,PageRank algorithms,etc[6–11].Although quantum algorithms are better than their classical counterparts in principle,the advantages of quantum algorithms are diminished when considering realistic physical conditions.To date,ion traps,atoms and superconducting qubits[12–14]have usually been used as a platform to realize quantum information tasks.These systems are quite sensitive to environmental dissipation.The quantum coherence of a system is weak if an external disturbance can destroy it[15,16],which is a major obstacle to quantum computation.Therefore,it is important to study how to implement a quantum computation accompanied by environmental dissipation.

The interactions between quantum systems and environments can be classified into various noises,such as memoryless white noise where the environment is often Markovian,and color noise with memory in which the environment behaves in a non-Markovian way[15,16].Many studies illustrate the role played by the environment as a simple Markovian one and obtain similar results between experimental outcomes and theoretical analysis[15,17,18].However,recent results reveal that non-Markovian scenarios also widely exist in reality.Typical examples include a single trapped ion interacting with an engineered reservoir[19,20],spontaneous emission atomic dynamics in photonic crystals[21],microcavities coupling with a coupled-resonator optical waveguide or photonic crystals[22,23],etc.The essential difference between Markovian and non-Markovian environments lies in whether the probability or energy can flow back from the environment to the quantum system.Studies have demonstrated that the dynamics of the quantum system are quite different between Markovian and non-Markovian scenarios[24–30].Therefore,in the non-Markovian case,the environment cannot be viewed as a leakage only,but it is capable of intentionally controlling the interacting quantum system[19,20,22,30].Recently,dissipative quantum-state engineering and quantum computation have attracted much attention.A large variety of strongly correlated states can be realized through dissipation[31].A mechanical oscillator cooled close to its ground state is revealed by controlling the coupling to the dissipation[32].A dissipation-assisted proposal to transfer an arbitrary quantum-state directionally is provided[33].By engineering the steady-state of a sensor,quantum sensing under dissipation is realized[34].Highfidelity nonclassical states are generated by dissipative quantum-state engineering[35],and autonomous quantumstate transfer over a long distance is achieved[36].The above discussion motivates us to consider whether we can carry out a quantum algorithm accurately even if the influences from the environment are not negligible.

In this paper,we implement a fast quantum search by engineering the surrounding environment of the quantum system.A platform for fast quantum search is constructed with two-level atoms.Through engineering the interaction between quantum systems and non-Markovian environments,quantum search algorithms can be run efficiently due to the memory backflow.For comparison,we also show that the quantum search cannot be executed in the Markovian environment due to the irreversible dissipation.Finally,we discuss the possible experimental realizations of the fast quantum search.A quantum search based on ultracold atoms is introduced in detail.

2.Review of fast quantum search

The searching problem aims to find the target data point in one unsorted database.If the number of data points in the database isN,the success probability of finding the target data point is 1/Nwith a random guess.The average time of queries to find the target data point isN/2,when considering the time of the random guess is just‘1’in the best case andNin the worst case.When a quantum correlation was introduced into the algorithms,Grover developed a quantum search algorithm from the quantum circuit model[4].It has been verified analytically that the target data point can be found with considerable probability through the use of orderqueries.Some groups have experimentally demonstrated such results in different platforms,e.g.nuclear magnetic resonance[37,38],optical implementation[39],ion trap[40],nitrogenvacancy centers[41]and superconducting systems[42].The involved numbers of data points in these experimental demonstrations are not large enough,whereas small decoherence in each component may accumulate into large decoherence and affect search results when the quantum systems become larger.The disappearance of quantum coherence may lead to wrong answers in the search outcome.

Recently,researchers verified that quantum speedup can also be reflected in the continuous-time quantum walk(CTQW)search algorithms on the graphs[6–9].Compared to those in Grover’s search algorithms,there is no need for logic gate operations in the CTQW search algorithms.The theoretical results[8]have shown that for oned-dimensional cubic lattice,the target vertex in the graph can be found at the time of orderwithd>4,at the time of orderwithd=4,and no speedup withd<4.In addition,researchers found that for graphs with low connectivity[6,7,9],the target vertex was also found through the delicate design of the transition rate among the adjacent vertices in the graphs.A typical example is the joined complete graph[7].Recent investigations have verified that a fast quantum search can be realized in such a graph having low connectivity,which was previously thought impossible.A diagram of this joined complete graph is shown in figure 1.

As shown in figure 1,the target vertex is drawn in red and labeled as‘1’.The left and right parts of these graphs are two complete graphs that containN/2 vertices.To illustrate theNvertices in the graph,we use dotted lines to represent enormous connections between every two vertices in the complete graphs.The left and right complete graphs are connected by only one edge,so we use a solid line to indicate this.For this graph,we can use computation basis states|ai〉i=1,…,N.The state |ai〉 iswhere theith element is nonzero.In the description of the graph,this state corresponds to theith vertex.We choose the first vertex as the target vertex for convenience.Thus,the target vertex isConsidering the transition rate as γ,the Hamiltonian used for the fast quantum search isHg=-γA-|w〉〈w| where the adjacent matrixAdescribes the connections between the vertices.The term-|w〉〈w| is often regarded as the ‘oracle’ Hamiltonian.The HamiltonianHgis expressed in matrix form as,

In thisN×Nmatrix,the top leftN/2×N/2 matrix describes the interactions in the left complete graph,and the right bottomN/2×N/2 matrix shows the interactions in the right complete graph.In addition to these top left and right bottomN/2×N/2 matrices,only two elements in the remaining matrixHgare nonzero(theN/2-th row,the(N/2+1)-th column,and the(N/2+1)-th row,theN/2-th column in the matrix).These two elements represent the connection between theN/2-th vertex and(N/2+1)-th vertex in the joined complete graph.

When the perturbation method is employed,one can find the appropriate transition rate γ=2/Nto reach the optimal fast quantum search[7].The largest success probability to find the target vertex is 50%.

Even though the theoretical results have provided good performance in the quantum search on the graphs,only the related experimental demonstrations[43]with the simplest case have been reported recently.This is because the connections between vertices in the graphs are complicated,and easily affected by the surrounding environment.Under realistic conditions,the unavoidable dissipation diminishes the coherence and makes the system work at a steady condition within a short time[43,44].Quantum walk search algorithms under decoherence have been studied theoretically in detail[45].It is concluded that the existence of decoherence leads to more time and lower successful search probability in the search process.

Based on the discussion above,it is clearly shown that quantum search algorithms can have good performance in theory,but actual realizations may have strong limitations due to decoherence.Therefore,exploring how to execute fast quantum search algorithms under decoherence becomes an interesting task.An effective way is to use the existing quantum algorithms with consideration of decoherence and make every effort to reduce the influence of this decoherence.Recent work regarding the realization of quantum logic in a noisy environment motivates us to engineer dissipation for quantum search algorithms[30].It is necessary that we know the noise spectrum of the environment,and engineer the corresponding environment by using open quantum system theory.In our study,we focus on this method and ensure the effective operation of existing quantum algorithms.

3.Quantum search in atomic systems

In this section,we construct the joined complete graphs based on atomic ensembles to realize a fast quantum search.We consider an atomic system as illustrated in figure 2(a).The two internal states of each atom are depicted as spin up |↑〉 and spin down |↓〉.The whole system comprises two symmetric subsystems and each subsystem hasN/2 atoms.We assume that any two atoms in the subsystem have identical interactions γ.Each subsystem corresponds to a complete graph and the subsystems are connected through an atomic interaction γ,e.g.the interaction between theN/2-th and the(N/2+1)-th atoms in figure 2(a),and we assume that there are no interactions between the other atoms of the two subsystems.The atomic excitation(|↑〉)can be transferred among atoms through atomic interaction.Each time the excitation is transferred to atom 1(the red one in figure 2),the system can accumulate a π phase shift,which is just the functionality of Oracle in quantum search.The phase shift can be implemented by applying a magnetic field,which will be introduced in section 5 in detail.The Hamiltonian of the system can be written as,

4.Quantum search with dissipation

In the following,we will study quantum search in dissipative environments.The interactions between atomic systems and environments will be considered.We assume that the environment is quantized into a collection of harmonic oscillators with frequencies ω.The interactions between atoms and environments can be described as,

Markovian scenarios

In the Markovian approximation,the coupling spectrum|g(ω)|2of the environment is almost flat and independent of modes.This noise spectrum has been widely applied in the study of open quantum systems[15–18].We consider the spectrum of the environment as |g(ω)|2=Γ/π.After substituting |g(ω)|2into equation(A4)(appendix A),we obtain t hecorresponding time correlation functionu(t-t′)=2Γδ(t-t′).In the derivation ofu(t-t′),we have shifted the integral limit(0,+∞)of equation(A4)(appendix A)to(-ω↑↓,+∞),and extended the lower limit to-∞as a good approximation due to the large optical frequency ω↑↓.Therefore,the integral termsof equations(A3a)–(A3e)(appendix A),which describe the interaction between atoms and environments,can be replaced byWe can simulate the quantum search on atoms that are coupled with Markovian environments.The simulation results are shown in figure 4(red dashed lines).In the Markovian approximation,the environment is memoryless and the energy is irreversibly dissipated into the surroundings.It is found that the success probabilityP1=|C1(t)|2representing the probability for atoms in the marked state|1〉,decays exponentially due to the loss.Therefore,the quantum search cannot be executed with atoms coupled with Markovian environments.

Non-Markovian scenarios with Lorentzian spectra

We have studied quantum search in Markovian environments.Although the experiments can be well described with Markovian theory in many cases,color noise is required to describe the environment more precisely due to the complexity of the realistic environment[15,16,19–23].In many situations,the structure of environments cannot be ignored and one needs to consider the specific spectra|g(ω)|2.One of the common spectra for color noise is a Lorentzian spectrum,which is widely applied in atom-cavity systems[46–49],photonic crystals[21,48],etc.Lorentzian noise can also be shaped by filtering white noise with a cavity[50].Different from the Markovian scenarios,non-Markovian environments have memory effects and the energy leaked into the environments can flow back to the system.Furthermore,some good performances in quantum information processing under this Lorentzian noise have been reported.In the following,we study quantum search in non-Markovian environments and demonstrate that an ideal quantum search can be achieved by designing environments.A Lorentzian spectrum can be written as,

where Γ and λ represent the strength and spectral width of the coupling between the atomic transition and environments.In particular,the spectral width λ is inversely proportional to the memory time of environments.When λ tends to infinity,the environment becomes memoryless and the spectrum|g(ω)|2is equal to a constant value Γ/π.One can substitute equations(5)into(A4)(appendix A)and obtain the corresponding time correlation function:

By substituting equation(6)into the equations of motion(equations(A3a)–(A3e)in appendix A),we simulate quantum search on atoms in Lorentzian environments.As illustrated in figure 4,for Lorentzian spectra with finite widths λ,the success probabilitiesP1(blue solid lines)oscillate and decay slowly with time,which is completely different from the Markovian cases(red dashed lines).As previously stated,a narrower spectral width implies a stronger memory effect.As λ decreases,more energy that is dissipated into the environments can flow back to the system.Figures 5(a)and(c)exhibit the corresponding success probabilitiesP1under different spectral widths λ,when the atomic numbers areN=8 andN=16.From figure 5,one finds that the success probabilityP1increases as λ decreases.When the spectral width λ decreases to 0.001Γ,the success probability on a time scalecan almost be revived to 50%.Figures 5(b)and(d)describe the corresponding probability distributions for different λ,whenN=8,t=3.2 andN=16,t=4.4.The probabilityPEis the energy dissipated into the environment andPE=1-ΣjPj.As previously stated,in figures 5(b)and(d),less net energy lossPEoccurs as λ decreases.Furthermore,it is also found that the probability distribution may be influenced by the interaction between atoms and the environment.On the one hand,the probability distributions(λ=0.1Γ and λ=0.01Γ)that include couplings to the environment,are quite different from those in the ideal case(figures 3(b)and(c)),and on the other hand,different spectral widths λ result in various probability distributions.Specifically,when λ decreases to 0.001Γ,the probability distributionsPj(j=1,…,N)are almost the same as the distributions in figures 3(b)and(c).

Figure 1.Diagram of the joined complete graph.Target vertex is in red and labeled as‘1’.Other vertices in different colors represent different groups.For this joined complete graph,we can use a 5D subspace to obtain an optimal fast quantum search.Symbol‘…’denotes too many vertices,which are not shown.

Figure 2.(a)Illustration of the atomic system composed of two symmetric subsystems.Each subsystem comprises N/2 atoms,and each atom has two internal states,|↑〉and|↓〉.Atoms in the subsystem interact with each other through identical interactions γ.Two subsystems are coupled through the interaction between the N/2-th and the(N/2+1)-th atoms.(b)Specific example with eight atoms for the model depicted in(a).

Figure 3.Success probability P1=|C1(t)|2 and probability distribution for quantum search in the atomic system.(a)Probabilities P1 for N=8(blue solid line)and N=16(yellow solid line)atoms are illustrated,respectively.(b)Probability distribution Pj(j=1,…,N)for N=8 and t=3.2.(c)Probability distribution Pj(j=1,…,N)for N=16 and t=4.4.

Figure 4.Success probability P1=|C1(t)|2 for quantum search in the atomic system.Probabilities P1 correspond to Markovian(red dashed lines)and non-Markovian environments(blue solid lines)are presented,respectively.We assume the spectra of the non-Markovian environments are Lorentzian spectra.(a)Success probability for N=8,γ=0.25,Γ=1 and λ=Γ.(b)Success probability for N=16,γ=0.125,Γ=1 and λ=Γ.

Figure 5.Success probability P1=|C1(t)|2 and probability distribution for quantum search in the atomic system.In Lorentzian environments,the probabilities P1 and probability distributions Pj(j=1,…,N)and PE corresponding to different spectral widths λ=0.1Γ,λ=0.01Γ and λ=0.001Γ are presented,respectively.(a)Success probability for N=8 and γ=0.25.(b)Probability distribution for N=8, t=3.2 and γ=0.25.(c)Success probability for N=16 and γ=0.125.(d)Probability distribution for N=16, t=4.4 and γ=0.125.

It should be noted that the interaction between atoms and external environments has been considered in this section.From the above calculations,we find that,when couplings between atoms and environments are included,quantum noise usually causes negative effects for the implementation of the quantum search algorithm(as depicted in figures 4 and 5).Therefore,it is hard to realize fast quantum search in practical systems.However,our studies show that one can achieve a fast quantum search by manipulating the spectral width λ of the environment.A success probability of 50%is acquired on a time scaleBy comparison,the results in sections 2 and 3 only exist in ideal models,where the couplings between atoms and environments are excluded and the effect of quantum noise is ignored.Therefore,one needs to use an environmental engineering approach to realize fast quantum search in practical systems considering quantum noise.

5.Experimental realizations

In the following,we discuss the experimental realizations of fast quantum search.First,we show how to realize the ideal quantum search HamiltonianH0without consideration of the surrounding environment.As shown in figure 4,the ideal fast quantum search disappears when white noise is considered.This noise is commonly studied in quantum information experiments[15,17,18].Then,we provide a way to engineer the environment,which changes the white noise to the Lorentzian environment.The search Hamiltonian equation(2)can be obtained through Heisenberg XY interactions.The Heisenberg XY model,which has been intensively investigated in both theory and experiment,can be realized in cold atoms[51,52],quantum dot spins[53],cavity quantum electrodynamics[54],etc.

We consider the model in figure 2(b)as an illustration.Eight ultracold bosonic atoms are trapped inside an optical lattice.The four atoms on the right(left)side constitute vertices of a regular tetrahedron in 3D space.For sufficiently strong potential and low temperatures,the low-energy Hamiltonian is[51,52],

which is equivalent to the HamiltonianH0(equation(2))forN=8.Here,the Hilbert space forNatoms is 2N.In our realization withNatoms,we only make use of the first excitation subspace withNdimensions.The ‘oracle’ Hamiltonian is required when searching the target vertex on the graph.It is convenient to realize this Hamiltonian by the design of the distribution of magnetic field as stated above.Moreover,our design can realize a programable quantum search by changing the distribution of the magnetic field.We can achieve the quantum search of any vertex on the graph.

Since the atoms inevitably interact with external environments,the realistic systems are open quantum systems.In the previous discussion,we demonstrated that when a system is coupled with Lorentzian environments,one can realize fast quantum search by engineering environments.As reported in some experiments,the environments are treated as Markovian cases with white noise.The dynamics of the atomic system interacting with a Lorentzian environment can be equivalently described by the coherent coupling between the system and pseudomodes,with the latter leaking into an independent Markovian environment[46–48].Calculation details related to the dynamics of atoms within the pseudomode method are provided in appendix B.The frequency and decay rate of the pseudomode,which are determined by noise spectrum equation(5),are ω↑↓and 2λ,respectively(appendix B).The coupling strength between atoms and the pseudomode is(appendix B).It can easily be found that the equivalent coupling strength Ω gets weaker as the spectral width λ becomes smaller.Fewer atomic excitations are transferred to the pseudomode and dissipated,due to the net effect of energy backflow.Through narrowing the spectral width λ,the atomic system can be finally viewed as decoupled from the pseudomode,and one can thus realize an ideal quantum search.The Lorentzian environments can be experimentally constructed by leaving a lossy cavity in the Markovian environment,which can filter the input white noise into color noise with the Lorentzian spectrum[46–48,50].By manipulating the cavity parameters(e.g.,cavity transmissivity and reflectivity,quality factor,etc),one can engineer the Lorentzian environment.

6.Conclusion

We studied the realization of fast quantum search in atomic systems.Through constructing a joined complete graph in atoms,a fast quantum search of runtimeis realized with a success probability of 50%.Furthermore,we take into account the influence of dissipation,which arises due to the inevitable coupling of a system with its environment.When the system interacts with a Markovian environment,energy can be irreversibly leaked into external environments.The quantum speedup effect is washed out by dissipation,thus a fast quantum search cannot be achieved.However,a completely different phenomenon can arise in our engineered non-Markovian environments.Through engineering Lorentzian environments,one can re-implement an ideal fast quantum search due to the energy backflow from the environment to the system.Finally,we also discuss the possible experimental realizations based on ultracold atoms.As dissipation is one of the strongest adversaries in quantum computation,our work provides a possible path for realizing fast quantum search in practical systems.Our proposal here is based on engineering of the environment.Other ways to diminish decoherence may work well through engineering the system Hamiltonian.One representative method is dynamical decoupling,which has been widely applied in the preservation of coherence in quantum systems[61–66].When applying dynamic decoupling to our system,we need to engineer the incident Hamiltonian to overcome a certain kind of noise.We will study this in the near future.

Acknowledgments

This work was supported by the National Key R&D Program of China(Grant No.2017YFA0303800)and the National Natural Science Foundation of China(Grant Nos.11 604 014 and 11 974 046).

Appendix A.Time evolutions of atoms in dissipative environments

Appendix B.Description of the atomic dynamics with pseudomodes

ORCID iDs