Distributed exact Grover’s algorithm

Abstract

Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a distributed exact Grover’s algorithm (DEGA), which decomposes the original search problem into $\lfloor n/2\rfloor$ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover’s algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is $8(n\text{mod}2)+9$, which is less than the circuit depths of the original and modified Grover’s algorithms, $1+8\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ and $9+8\lfloor \frac{\pi }{4}\sqrt{2^n}-\frac{1}{2}\rfloor$, respectively. It only depends on the parity of $n$, and it is not deepened as $n$ increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.

Graphical abstract

Keywords

distributed quantum computation / search problem / distributed exact Grover’s algorithm (DEGA) / MindQuantum / the depolarization channel noise

1 Introduction

Localization is an interesting phenomenon of waves. The celebrated example is the Anderson localization, where free electrons (or classical wave) can be localized by the disorder induced interference [1, 2]. In some flat band lattices, free electrons can be localized without any disorder, and form a flat band [3–7]. This is the flat band localization (FBL), which results from the lattice geometry induced destructive interference of the electron wave.

The FBL is of special interest and has been intensively studied in last three decades. It was first noticed in electron lattice system [3], and has been generalized into various artificial lattice systems very recently [7–24]. Due to the quenched kinetic energy, it is predicted that the flat band electrons can be changed into ordered states (e.g., SDW) by tiny Coulomb interaction [4–6, 25–27]. Meanwhile, the topological flat bands may give rise to the fractional quantum hall states in the absence of magnetic field [28–30].

In this paper, we discover a new type of wave localization phenomenon in periodic wave systems, which can produce designed flat bands in a spatially continuous system. It clearly indicates that the interference induced FBL should a more general phenomenon of wave, which exists not only just in spatially discrete systems, i.e., the flat band lattices, but also in the spatially continuous systems. We first design a quasi one dimensional waveguide with a periodic confinement potential, e.g., electron waveguides (EWGs) on two dimensional electron gas (2DEG) as illustrated in Fig.1. Numerical calculations show that, if choosing proper shape of the confinement potential, electrons can be completely localized in an open waveguide and flat bands arise. We then illustrate that this unusual FBL actually results from the emergence of self-localized orbitals. Specifically, due to the periodicity of confinement potential, the EWG can be divided into unit cells, where each one is equivalent to an artificial atom (or a quantum dot). Correspondingly, the eigenfunctions of such atom can be viewed as the orbitals of the artificial atom. Because of the designed shape of potential, some peculiar orbitals have special spatial distributions (or interference patterns), which render themselves localized in the open EWG. These self-localized orbitals give rise to flat bands in the EWG. In principle, the self-localized orbital should be viewed as a new kind of compact localized state in spatially continuous wave system, which was first proposed in the flat band lattices [31, 32]. Importantly, since that the electron filling of the 2DEG is controllable, we can tune the Fermi level of the EWG to the position of flat band. Therefore, it offers an ideal platform to investigate the flat band induced correlated ground states, e.g., ferromagnetism, Wigner crystal, etc.

Fig.1 (a) Schematic of the electron waveguide (EWG) on 2DEG. The electrons are confined in a dark-colored region, and the dashed box indicates a unit cell of the waveguide. (b) One example of $U(r)$ in one unit cell. $U(r)$ is zero inside the waveguide (the gray region) and infinite outside. Here, $d$ = 52 nm, $h$ = 14 nm, $l$ = 26 nm. The corresponding band structure is given in (d). (c) is the $|{\varphi }_k(r){|}^2$ of the flat band (upper one) at the $\mathrm{\Gamma }$ (k = 0) point, marked as black dot in (d). (e) and (g) are two other EWGs, where $U(r)$ are of different shapes, and the corresponding band structures are given in (f) and (h), respectively. $|{\varphi }_k(r){|}^2$ of the flat band at the marked k point (black dot) are also plotted in (e) and (f). The geometry parameters for (e) and (f) are given in the Electronic Supplementary Materials.

Full size|PPT slide

Such FBL phenomenon is a general phenomenon of waves, and can arise in any wave system with proper boundary condition. Taking the electromagnetic wave for example, we design a metallic waveguide (MWG) array, and show that similar FBL can be readily observed in experiment. This self-localized electromagnetic mode is highly tunable, and is related to many intriguing optical applications, such as information transmission [33, 34], slow light [35] and bound states in continuum [36].

2 Flat bands in electron waveguides

The models we studied are illustrated in Fig.1. Here, we take the 2DEG system as the first example. The Hamiltonian is

(1)$H=-{\displaystyle \frac{{\hslash }^2}{2m}}{\mathrm{\nabla }}^2+U(r).$

The free electrons are confined by a periodic infinite potential well $U(r)$ to form an EWG, where several examples of $U(r)$ with different shape are given in Fig.1. $U(r)$ is periodic along the direction of the waveguide, so that we can define the unit cell of the EWG, as indicated by the dashed boxes. An example of $U(r)$ (in one unit cell) is given in Fig.1(b), which corresponds to the EWG in Fig.1(c). $U(r)$ is zero inside the EWG (grey region) and infinitely large outside. In experiments, this confinement potential on 2DEG can be achieved by applying a proper gate voltage or lithography. Note that the required parameters here should be within the present experiment capability. Numerically, we use the finite difference method to solve the Schrödinger equation with proper boundary conditions [37]. Since it is a periodic system, we can calculate the energy bands and the Bloch wave functions. The effective mass is $0.067m_e$, which is the value of AsGa 2DEG.

We plot the energy bands for the EWGs with different shapes in Fig.1. In all those designed EWGs, we get flat bands (or nearly flat band) with different band structures. It is the central result of this work. For example, with the $U(r)$ in Fig.1(c), the lowest seven bands are plotted in Fig.1(d). In such EWG, there are two flat bands (red solid lines), while others are dispersive (blue solid lines). Interestingly, the flat bands are separated away from the dispersive bands with gaps from several to tens meV. The gaps can be further tuned by changing the size of the EWG. It means that, in this EWG, we can access the flat band states without any disturbances from other states. This offers great convenience to study the property of flat bands. To set the Fermi level in the upper flat band, the required charge density is about $1.2\times {10}^{-11}$ ${\mathrm{c}\mathrm{m}}^{-2}$, which is a reasonable value in experiment [38]. Actually, various kinds of flat bands can be obtained by this method with different $U(r)$. In Fig.1(f), a single flat band emerges, where the potential $U(r)$ is given in Fig.1(e). We can even get a flat band with band inversion and hybridization with other dispersive band, as shown in Fig.1(h), where the corresponding $U(r)$ is given in Fig.1(g). The band hybridization here can induce a tiny bump to the flat band in Fig.1(h), so that we actually get a partially or nearly flat band here. Note that the wave function in the bump region is different from that in the flat region of this band [39]. The flat band wave functions $|{\varphi }_k(r){|}^2$ at the marked k points [black dots in Fig.1(d, f, h)] are plotted in Fig.1(c, e, g), respectively. In Fig.1, the calculated wave functions at all the k points in the flat region of each flat band are the same.

Obviously, this new FBL phenomenon in waveguide is beyond the scope of the well-known flat band lattice models, such as Lieb lattice and Kagome lattice, since that it occurs in a spatial continuous systems. It implies that there is a geometry induced wave localization mechanism in the spatially continuous system.

3 Self-localized orbitals

To understand this exotic FBL phenomenon, we first introduce the concept of artificial orbital. We take the case in Fig.1(c) and (d) as a typical example. Basically, each unit cell of the EWG can be viewed as a single artificial atom (or a quantum dot), in which electrons are confined in a potential like in Fig.2(a). Then, these artificial atoms (unit cells) are connected to construct an atomic chain, i.e., EWG. Note that the potential for an isolated atom [Fig.2(a)] is different from that in the EWG [Fig.1(b)] in boundary condition. For a single isolated atom, the potential is spatially closed, such that electrons in the atom have no way to escape. However, as the atoms are connected, the potential well is opened at the connecting edges [Fig.1(b)], through which electrons can transport to adjacent atoms. In a single artificial atom, the energy of eigenstates are discrete due to the spatial confinement, and the corresponding eigenfunctions present different interference patterns. These eigenfunctions are just the orbitals of the artificial atom. Meanwhile, in the EWG, because of the overlap between the orbitals, the energy levels of the artificial atom are transformed into the energy bands of the EWG. This orbital picture works quite well here. And we would like to mention that similar artificial electron orbitals induced by 2D confinement potential have been studied theoretically [8, 9, 40], and observed in recent experiments [10, 41].

Fig.2 (a) $U(r)$ of an isolated artificial atom (or quantum dot). The geometry parameters are the same as Fig.1(b). $U(r)$ is zero inside the atom (gray region) and infinite outside. (b) and (c) are the wave functions $|\varphi (r){|}^2$ of the fourth and sixth orbitals (eigenstates) in the isolated atom, respectively. (d) is the wave function $|{\varphi }_k(r){|}^2$ of the sixth band (upper flat band) at $\mathrm{\Gamma }$ point ($k=0$) for the EWG in Fig.1(d), while (e) is that of the fourth band (dispersive). We plot one unit cell in (d) but two unit cells in (e) in order to show the bond between two adjacent orbitals.

Full size|PPT slide

Because of the peculiar interference patterns, some orbitals in this artificial atom are self localized, which produce the flat bands in the EWG. In Fig.2(b), we plot the wave function of the fourth artificial orbital in a single atom, which corresponds to the fourth band (dispersive) in Fig.1(d). And, for the upper flat band, i.e., the sixth bands in Fig.1(d), the corresponding artificial orbital (the sixth orbital [42].) is given in Fig.2(c). Comparing the two orbitals, it can be found that the flat band orbital is localized in a region very far away from the connecting edges, because of its unique interference pattern. It implies that, when atoms are connected, the overlap between the flat band orbitals on adjacent atoms is zero (or nearly zero), and thus electrons in this orbital actually are strictly localized in each unit cell. We name this kind of artificial orbital self-localized orbital. The self-localized orbital is the reason why the EWG has flat bands. To make this point clear, in Fig.2(d), we plot the Bloch wave function of the upper flat band (the wave functions at all the k points in this flat band are the same). We see that the self-localized orbital of the artificial atom [Fig.2(c)] and the corresponding flat band Bloch wave function in EWG [Fig.2(d)] are exactly the same. In contrast, for the dispersive energy bands like the fourth band in Fig.1(d), we can clearly see that bonds are formed in between the adjacent atoms [Fig.2(e)].

The self-localized orbital is a pure interference phenomenon. It should be noted that the self-localized orbital induced flat bands here are different from the trivial flat bands, which result from the potential barrier. For example, in real atoms, the energy of core electrons are lower than that of valence electrons, such that the core electrons are tightly bound to the nucleus due to the confinement of Coulomb potential. The electrons can not hop between the adjacent real atoms is because the large confinement potential, which results in the vanishing overlap of the orbitals from the adjacent atoms. This produces a trivial flat band for the core electrons, which results from the potential barrier rather than the wave interference. In our model, the potential inside the EWG is flat, such that there is no potential barrier to obstruct the moving of electrons inside the EWG. Thus, the self localization induced flat band is a pure interference phenomenon which does not need the help of the confinement potential, and thus is different from real atoms. In this sense, the self-localized orbital here can be viewed as a compact localized state in the spatially continuous systems, compared with the case of flat band lattice [31].

The self-localized orbitals, as well as the corresponding flat bands, are controlled by the local geometry of the $U(r)$, as shown clearly in Fig.1(c). Such highly tunable flat bands are very useful for the future application of the flat bands. Note that, similar self-localized orbits also appear in the $U(r)$ as shown in Fig.1(e) and (g) [43]. In the experiment, we suggest to use the etching technique to fabricate the electron waveguide on the 2DEG, which should correspond to a sharp potential well model. Besides the sharp potential model in Fig.1, we have checked the corresponding finite potential well model as well, and the results show that the flat band localization is rather robust.

4 FBL of electromagnetic waves

From the mathematical point of view, the self-localized orbital should be viewed as a spatially localized solution of wave equation in an open structure, distinct from the common plane wave (spatially extended) and the standing wave (in a closed structure). Thus, in principle, the FBL phenomenon can appear in any wave systems, described by the wave equation, with proper boundary condition.

To illustrate this idea, we give the second example of FBL in electromagnetic wave system. Concretely, we show that the self-localized orbital induced flat bands of electromagnetic waves can be realized in MWG array, see Fig.3(a). The MWG array is infinitely long along the z direction, and the cross-section in x−y plane has a similar shape as that in Fig.1(c). Here, we consider the TE modes where the electric field has only one component along z-axis, as given by $E_z(x,y,z)=E_z(x,y)\exp (-\mathrm{i}{k}_{z}z)$. Accordingly, $E_z(x,y)$ in the waveguide obeys the equation as follows:

Fig.3 (a) Schematic of the metallic waveguide array, where the shape of the cross section of one unit cell in x−y plane is given in (b). In (b), the geometry of each unit cell is determined by d, l, h, where d is the lattice constant, h is the height between the bottom and the lowest upper surface, l is the hight of the bump of the upper surface. The electromagnetic wave propagate along z-axis, and can leak from one waveguide to the neighbouring waveguide in the x−y plane; three different waveguide arrays, i.e., labelled as w1, w2, w3, are examined, see the mode profiles ($E_z$) in (c, e, g) and the band diagram in (d, f, h) for w1, w2, w3. The geomentric parameters for w1, w2, w3 are given by as follows, $d/l/h$ = 16/8/5 cm for w1, $d/l/h$ =16/8/9.2 cm for w2, $d/l/h$ = 16/8/11.2 cm for w3.

Full size|PPT slide

(2)$({\mathrm{\nabla }}^2+k_0^2)E_z=k_0^2{n}_{eff}^2{E}_z,$

where $k_0=2\pi /{\lambda }_0$, $n_{eff}=k_z/k_0$, and ${\lambda }_0$ is vacuum wavelength. Here, $n_{eff}$ can be determined by the eigenvalue of this equation, and $n_{eff}^2$ corresponds to the energy in Schrödinger equation. For the MWG, the boundary condition is $E_z=0$. Eq. (2) is analogous to the Schrödinger equation, and the shape of the MWG array mimics the confinement potential $U(r)$ in the EWG in Fig.1(c). Thus, it can be expected that TE modes here have similar behaviours as the electrons in the EWG. Note that there are also TM modes in the waveguide, which is not discussed. The band structure of the MWG array is calculated using a commercial software package: COMSOL MULTIPHYSICS.

As expected, the numerical results unambiguously show that the flat bands of electromagnetic wave also exist in such MWG arrays, as given in Fig.3. In order to facilitate the comparison, we plot three cases, where the MWG geometry parameters $l$, $d$ are fixed, and different values of $h$ are used, as sketched in Fig.3(b). In Fig.3(c, e, g), we set $h=5,9.2,11.2$ $\mathrm{c}\mathrm{m}$, respectively. And the band diagrams are given in Fig.3(d, f, h) accordingly. All the bands for TE (TM) modes are plotted as red solid (blue dashed) lines in Fig.3(d−h). In Fig.3(c) and (d), the TE modes (see the red solid lines) have very similar band structure as that of the EWG in Fig.1(d). The eigen-field at the marked k point of the flat band [black dot in Fig.3(d)] is plotted in Fig.3(c), which also has a similar mode profile as the flat band wave function in EWG. The flat bands indicate that now the corresponding TE mode is localized along the x direction due to the self localization phenomenon. When we change the geometry of confinement, the artificial orbitals are changed and we get different band structure. In Fig.3(e) and (f), we enlarge $h$ to $9.2$ $\mathrm{c}\mathrm{m}$ and the band structure is fundamentally changed. Interestingly, the third band becomes flat here, while the former flat bands in Fig.3(d) are changed to be dispersive. We also plot the eigen-field of the flat band in Fig.3(e), and we see a rather different self-localized orbital. If the height $h$ becomes larger than a critical value, e.g., $h=11.2$ cm in Fig.3(g) and (h), all the bands are dispersive and the localization phenomenon vanishes. Finally, we emphasize that, though the designed MWG array above is for the microwave region, similar phenomenon can occur for the electromagnetic waves with scaled wavelength.

At last, we give a short discussion about the flatness of these flat bands resulted from the self-localized orbitals. An intuitive understanding is that, if the self-localized orbital is completely localized like the compact localized state in the flat band lattice, the resulted flat band should be perfect flat. However, the flat bands as well as the self-localized orbitals in this manuscript are all got by numerical methods, and an analytic proof about the perfect flatness is still lack. Taking the flat bands in Fig.1(d) for example, the numerical deviation is tiny (much smaller than 1 meV), which may come from the numerical errors. We should cautiously understand them as “nearly flat bands” in present circumstances. Even so, these nearly flat bands are much flatter than the electron flat bands in real materials, because that the long range hopping always exist in real materials and will bend the flat bands (based on some flat band lattices model). In addition, such self-localized flat bands are stable against the small potential disturbance, as along as it does not drastically modify the spatial distribution of the wave function. With similar method, we can also get partially flat bands as shown in Fig.1(h) and Fig.3(g).

5 Summary

In summary, we illustrate that wave in a periodic system can be completely localized by forming some kinds of self-localized orbitals. It can be used to produce electron flat bands in solid state systems, which may give rise to novel correlated phenomena. Though the two examples are quasi one dimension, we argue that similar phenomenon can also arise in two and three dimension.Actually, we have already designed and calculated some 2D and 3D structures with similar principle. The preliminary calculation results have already shown that such flat band localization phenomenon can also occur in 2D and 3D systems. Considering the vast literature about the flat band lattices, great flat band related phenomena can be expected in the wave systems with the self-localized orbitals, e.g., the interplay between the flat band and nonlinear terms [44].

References

[1] P. Benioff. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. J. Stat. Phys., 1980, 22(5): 563

[2] P. Benioff. Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys., 1982, 29(3): 515

[3] D. Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A, 1985, 400(1818): 97

[4] D. Deutsch, R. Jozsa. Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A, 1992, 439(1907): 553

[5] E.BernsteinU. Vazirani, Quantum complexity theory, in: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC’93), 1993, pp 11–20

[6] D. R. Simon. On the power of quantum computation. SIAM J. Comput., 1997, 26(5): 1474

[7] P.W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in: Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp 124–134

[8] L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 1997, 79(2): 325

[9] A. W. Harrow, A. Hassidim, S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 2009, 103(15): 150502

[10] D.ChristophH. Peter, A quantum algorithm for finding the minimum, arXiv: quant-ph/9607014v2 (1996)

[11] H. Ramesh, V. Vinay. String matching in O~(n+m) quantum time. J. Discrete Algorithms, 2003, 1(1): 103

[12] A.AmbainisK. BalodisJ.Iraids, ., Quantum speedups for exponential-time dynamic programming algorithms, in: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Diego: SIAM, 2019, pp 1783–1793

[13] A.AndrisL. Nikita, Quantum algorithms for computational geometry problems, in: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2020

[14] G. Brassard, P. Hoyer, M. Mosca. . Quantum amplitude amplification and estimation. Contemp. Math., 2002, 305: 53

[15] Z. J. Diao. Exactness of the original Grover search algorithm. Phys. Rev. A, 2010, 82(4): 044301

[16] G. L. Long. Grover algorithm with zero theoretical failure rate. Phys. Rev. A, 2001, 64(2): 022307

[17] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79

[18] J. I. Cirac, P. Zoller. Quantum computations with cold trapped ions. Phys. Rev. Lett., 1995, 74(20): 4091

[19] C. Y. Lu, X. Q. Zhou, O. Guhne, W. B. Gao, J. Zhang, Z. S. Yuan, A. Goebel, T. Yang, J. W. Pan. Experimental entanglement of six photons in graph states. Nat. Phys., 2007, 3(2): 91

[20] Y. Makhlin, G. Schön, A. Shnirman. Quantum-state engineering with Josephson-junction devices. Rev. Mod. Phys., 2001, 73(2): 357

[21] J. Berezovsky, M. H. Mikkelsen, N. G. Stoltz, L. A. Coldren, D. D. Awschalom. Picosecond coherent optical manipulation of a single electron spin in a quantum dot. Science, 2008, 320(5874): 349

[22] R. Hanson, D. D. Awschalom. Coherent manipulation of single spins in semiconductors. Nature, 2008, 453(7198): 1043

[23] H.BuhrmanH. Röhrig, Distributed quantum computing, in: Mathematical Foundations of Computer Science 2003: 28th International Symposium, Berlin Heidelberg, Springer, 2003, pp 1–20

[24] A. Yimsiriwattan, Jr Lomonaco. Distributed quantum computing: A distributed Shor algorithm. Quantum Inf. Comput. II., 2004, 5436: 360

[25] R. Beals, S. Brierley, O. Gray. . Efficient distributed quantum computing. Proc. R. Soc. A, 2013, 469(2153): 0120686

[26] K. Li, D. W. Qiu, L. Li, S. Zheng, Z. Rong. Application of distributed semiquantum computing model in phase estimation. Inf. Process. Lett., 2017, 120: 23

[27] J. Avron, O. Casper, I. Rozen. Quantum advantage and noise reduction in distributed quantum computing. Phys. Rev. A, 2021, 104(5): 052404

[28] D.W. QiuL. LuoL.G. Xiao, Distributed Grover’s algorithm, arXiv: 2204.10487v3 (2022)

[29] J. W. Tan, L. G. Xiao, D. W. Qiu, L. Luo, P. Mateus. Distributed quantum algorithm for Simon’s problem. Phys. Rev. A, 2022, 106(3): 032417

[30] L.G. XiaoD. W. QiuL.LuoP.Mateus, Distributed Shor’s algorithm, Quantum Inf. Comput. 23(1&2), 27 (2023)

[31] L.G. XiaoD. W. QiuL.Luo, ., Distributed quantum−classical hybrid Shor’s algorithm, arXiv: 2304.12100 (2023)

[32] X.ZhouD. W. QiuL.Luo, Distributed exact quantum algorithms for Bernstein−Vazirani and search problems, arXiv: 2303.10670 (2023)

[33] H.LiD.W. Qiu L.Luo, Distributed exact quantum algorithms for Deutsch−Jozsa problem, arXiv: 2303.10663 (2023)

[34] MindQuantum, URL: gitee.com/mindspore/mindquantum, 2021

[35] M.A. NielsenI.L. Chuang, Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, 2002

Declarations

The authors declare that they have no competing interests and there are no conflicts.

Data availability statement

No data associated in the manuscript.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61572532 and 61876195) and the Natural Science Foundation of Guangdong Province of China (No. 2017B030311011).

RIGHTS & PERMISSIONS

2023 Higher Education Press