Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Quantum Information Processing
Published in: Quantum Information Processing 7/2021

01-07-2021

Implementation of efficient quantum search algorithms on NISQ computers

Authors: Kun Zhang, Pooja Rao, Kwangmin Yu, Hyunkyung Lim, Vladimir Korepin

Published in: Quantum Information Processing | Issue 7/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Despite the advent of Grover’s algorithm for the unstructured search, its successful implementation on near-term quantum devices is still limited. We apply three strategies to reduce the errors associated with implementing quantum search algorithms. Our improved search algorithms have been implemented on the IBM quantum processors. Using them, we demonstrate three- and four-qubit search algorithm with higher average success probabilities compared to previous works. We present the successful execution of the five-qubit search on the IBM quantum processor for the first time. The results have been benchmarked using degraded ratio, which is the ratio between the experimental and the theoretical success probabilities. The fast decay of the degraded ratio supports our divide-and-conquer strategy. Our proposed strategies are also useful for implementation of quantum search algorithms in the post-NISQ era.
previous article Quantum sealed-bid auction protocol for simultaneous ascending auction with GHZ states
next article Embedding of complete graphs in broken Chimera graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
1.
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T.C., Mutus, J., Fowler, A.G., Campbell, B., et al.: Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature 508(7497), 500 (2014)ADSCrossRef
2.
Ballance, C.J., Harty, T.P., Linke, N.M., Sepiol, M.A., Lucas, D.M.: High-fidelity quantum logic gates using trapped-ion hyperfine qubits. Phys. Rev. Lett. 117(6), 060504 (2016)ADSCrossRef
3.
Figgatt, C., Maslov, D., Landsman, K.A., Linke, N.M., Debnath, S., Monroe, C.: Complete 3-qubit grover search on a programmable quantum computer. Nat. Commun. 8(1), 1918 (2017)ADSCrossRef
4.
Google AI Quantum, et al.: Hartree-fock on a superconducting qubit quantum computer. Science 369(6507), 1084–1089 (2020)
5.
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Sergio, B., Fernando, G.S.L., Buell, D.A., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)ADSCrossRef
6.
Zhong, H.-S., Wang, H., Deng, Y.-H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Qin, J., Wu, D., Ding, X., Hu, Y., et al.: Quantum computational advantage using photons. Science 370(6523), 1460–1463 (2020)ADS
7.
Nielsen, M.A., Chuang, I.L.: Quantum computation and quantum information, (2010)
8.
Preskill, J.: Quantum computing in the nisq era and beyond. Quantum 2, 79 (2018)CrossRef
9.
Cross, A.W., Bishop, L.S., Sheldon, S., Nation, P.D., Gambetta, J.M.: Validating quantum computers using randomized model circuits. Phys. Rev. A 100(3), 032328 (2019)ADSCrossRef
10.
Bharti, K., Cervera-Lierta, A., Kyaw, T.H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J.S., Menke, T., Mok, W.-K., Sim, S., Kwek, L.-C., Aspuru-Guzik, A.: Noisy intermediate-scale quantum (nisq) algorithms. arXiv preprint arXiv:​2101.​08448, (2021)
11.
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)ADSCrossRef
12.
13.
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)MathSciNetCrossRef
14.
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195–202 (2017)ADSCrossRef
15.
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik: Prog. Phys. 46(4–5), 493–505 (1998)ADSCrossRef
16.
Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)ADSCrossRef
17.
Grassl, M., Langenberg, B., Roetteler, M., Steinwandt, R.: Applying grover’s algorithm to aes: quantum resource estimates. In: Post-Quantum Cryptography, pp. 29–43. Springer, (2016)
18.
Kim, P., Han, D., Jeong, K.C.: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to aes and sha-2. Quantum Inf. Process. 17(12), 339 (2018)ADSMathSciNetCrossRef
19.
Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on aes and lowmc. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 280–310. Springer, (2020)
20.
Wang, Y., Krstic, P.S.: Prospect of using grover’s search in the noisy-intermediate-scale quantum-computer era. Phys. Rev. A 102(4), 042609 (2020)ADSCrossRef
21.
Kato, G.: Grover-algorithm-like operator using only single-qubit gates. Phys. Rev. A 72(3), 032319 (2005)ADSCrossRef
22.
Tulsi, A.: Faster quantum searching with almost any diffusion operator. Phys. Rev. A 91(5), 052307 (2015)ADSCrossRef
23.
Jiang, Z., Rieffel, E.G., Wang, Z.: Near-optimal quantum circuit for grover’s unstructured search using a transverse field. Phys. Rev. A 95(6), 062317 (2017)ADSCrossRef
24.
Grover, L.K., Radhakrishnan, J.: Is partial quantum search of a database any easier? In: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, pp. 186–194. ACM, (2005)
25.
26.
27.
Grover, L.K.: Trade-offs in the quantum search algorithm. Phys. Rev. A 66(5), 052314 (2002)ADSCrossRef
28.
Briański, M., Gwinner, J., Hlembotskyi, V., Jarnicki, W., Pliś, S., Szady, A.: Introducing structure to expedite quantum search. arXiv preprint arXiv:​2006.​05828, (2020)
29.
Zhang, K., Korepin, V.E.: Depth optimization of quantum search algorithms beyond grover’s algorithm. Phys. Rev. A 101(3), 032346 (2020)ADSMathSciNetCrossRef
30.
31.
Mandviwalla, A., Ohshiro, K., Ji, B.: Implementing grover’s algorithm on the ibm quantum computers. In: 2018 IEEE International Conference on Big Data (Big Data), pp. 2531–2537. IEEE, (2018)
32.
Gwinner, J., Briański, M., Burkot, W., Czerwiński, Ł., Hlembotskyi, V.: Benchmarking 16-element quantum search algorithms on ibm quantum processors. arXiv preprint arXiv:​2007.​06539, (2020)
33.
34.
Hlembotskyi, V., Burczyński, R., Jarnicki, W., Szady, A., Tułowiecki, J.: Efficient unstructured search implementation on current ion-trap quantum processors. arXiv preprint arXiv:​2010.​03841, (2020)
35.
Grover, L.K.: Quantum computers can search rapidly by using almost any transformation. Phys. Rev. Lett. 80(19), 4329 (1998)ADSCrossRef
36.
Brassard, G., Hoyer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. Contemp. Math. 305, 53–74 (2002)MathSciNetCrossRef
37.
Almazrooie, M., Samsudin, A., Abdullah, R., Mutter, K.N.: Quantum reversible circuit of aes-128. Quantum Inf. Process. 17(5), 112 (2018)MathSciNetCrossRef
38.
Langenberg, B., Pham, H., Steinwandt, R.: Reducing the cost of implementing aes as a quantum circuit. Technical report, Cryptology ePrint Archive, Report 2019/854, (2019)
39.
Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995)ADSCrossRef
40.
41.
Korepin, V.E., Vallilo, B.C.: Group theoretical formulation of a quantum partial search algorithm. Prog. Theor. Phys. 116(5), 783–793 (2006)ADSMathSciNetCrossRef
42.
Gingrich, R.M., Williams, C.P., Cerf, N.J.: Generalized quantum search with parallelism. Phys. Rev. A 61(5), 052313 (2000)ADSCrossRef
43.
Maslov, D.: Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization. Phys. Rev. A 93(2), 022311 (2016)ADSCrossRef
44.
Song, G., Klappenecker, A.: Optimal realizations of simplified toffoli gates. Quantum Inf. Comput. 4(5), 361–372 (2004)MathSciNetMATH
45.
Tannu, S.S., Qureshi, M.: Ensemble of diverse mappings: Improving reliability of quantum computers by orchestrating dissimilar mistakes. In: Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pp. 253–265 (2019)
Metadata
Title
Implementation of efficient quantum search algorithms on NISQ computers
Authors
Kun Zhang
Pooja Rao
Kwangmin Yu
Hyunkyung Lim
Vladimir Korepin
Publication date
01-07-2021
Publisher
Springer US
Published in
Quantum Information Processing / Issue 7/2021
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-021-03165-2

Other articles of this Issue 7/2021

Quantum Information Processing 7/2021 Go to the issue

OriginalPaper

Two-time correlation functions beyond quantum regression theorem: effect of external noise

OriginalPaper

Cryptanalysis and improvement of a semi-quantum private comparison protocol based on Bell states

OriginalPaper

An improved quantum algorithm for support matrix machines

OriginalPaper

Process tomography of robust dynamical decoupling with superconducting qubits

OriginalPaper

Characterization of quantum entanglement via a hypercube of Segre embeddings

OriginalPaper

Cellular automaton simulation of the quantum Hotelling game with reservation cost