nach oben

Quantum Information Processing

Erschienen in:

01.04.2024

Quantum search by continuous-time quantum walk on t-designs

verfasst von: Pedro H. G. Lugão, Renato Portugal

Erschienen in: Quantum Information Processing | Ausgabe 4/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This work examines the time complexity of quantum search algorithms on combinatorial t-designs with multiple marked elements using the continuous-time quantum walk. Through a detailed exploration of t-designs and their incidence matrices, we identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms. These graphs have adjacency matrices with eigenvalues and eigenvectors that can be determined algebraically and are also suitable for analysis in the multiple-marked vertex scenario. We show that the continuous-time quantum walk on certain symmetric t-designs achieves an optimal running time of \(O\left( \sqrt{n}\right) \), where n is the number of points and blocks, even when accounting for an arbitrary number of marked elements. Upon examining two primary configurations of marked elements distributions, we observe that the success probability is consistently o(1), but it approaches 1 asymptotically in certain scenarios.

Vorheriger Artikel Secure mutual authentication quantum key agreement scheme for two-party setting with key recycling

Nächster Artikel Asymmetric controlled cyclic quantum teleportation of two, three and four qubit states with optimal quantum resources

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)MathSciNetCrossRefADS

Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)CrossRefADS

Marsh, S., Wang, J.B.: Combinatorial optimization via highly efficient quantum walks. Phys. Rev. Res. 2, 023302 (2020)CrossRef

Kadian, K., Garhwal, S., Kumar, A.: Quantum walk and its application domains: a systematic review. Comput. Sci. Rev. 41, 100419 (2021)MathSciNetCrossRef

Portugal, R.: Quantum Walks and Search Algorithms, 2nd edn. Springer, Cham (2018)CrossRef

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

Philipp, P., Tarrataca, L., Boettcher, S.: Continuous-time quantum search on balanced trees. Phys. Rev. A 93, 032305 (2016)MathSciNetCrossRefADS

Tanaka, H., Sabri, M., Portugal, R.: Spatial search on Johnson graphs by continuous-time quantum walk. Quantum Inf. Process. 21(2), 74 (2022)MathSciNetCrossRefADS

Stinson, D.R.: Combinatorial Designs: Constructions and Analysis. Springer, New York (2004)

10.

Beth, T., Jungnickel, D., Lenz, H.: Design Theory, vol. 1, 2nd edn. Cambridge University Press, Cambridge (1999)CrossRef

11.

Rothaus, O.S.: On “bent’’ functions. J. Comb. Theory Ser. A 20(3), 300–305 (1976)CrossRef

12.

Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 012304 (2009)CrossRefADS

13.

Ambainis, A., Emerson, J.: Quantum t-designs: t-wise independence in the quantum world. In: Twenty-second annual IEEE conference on computational complexity (CCC’07), pp. 129–140 (2007)

14.

Emerson, J., Alicki, R., Życzkowski, K.: Scalable noise estimation with random unitary operators. J. Opt. B Quantum Semiclassical Opt. 7(10), S347 (2005)MathSciNetCrossRefADS

15.

Godsil, C., Royle, G.F.: Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer, New York (2001)

16.

Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A 67(5), 052307 (2003)CrossRefADS

17.

Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett. 114(11), 110503 (2015)CrossRefADS

18.

Pan, N., Chen, T., Sun, H., Zhang, X.: Electric-circuit realization of fast quantum search. Research 2021, 9793071 (2021)CrossRefADS

19.

Ji, T., Pan, N., Chen, T., Zhang, X.: Fast quantum search of multiple vertices based on electric circuits. Quantum Inf. Process. 21(5), 172 (2022)CrossRefADS

20.

Ji, T., Pan, N., Chen, T., Zhang, X.: Quantum search of many vertices on the joined complete graph. Chin. Phys. B 31(7), 070504 (2022)CrossRefADS

21.

Wong, T.G.: Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf. Process. 15(4), 1411–1443 (2016)MathSciNetCrossRefADS

22.

Bezerra, G.A., Lugão, P.H.G., Portugal, R.: Quantum-walk-based search algorithms with multiple marked vertices. Phys. Rev. A 103, 062202 (2021)MathSciNetCrossRefADS

23.

Lugão, P.H.G., Portugal, R., Sabri, M., Tanaka, H.: Multimarked spatial search by continuous-time quantum walk. arXiv:2203.14384 (2022)

24.

Apers, S., Chakraborty, S., Novo, L., Roland, J.: Quadratic speedup for spatial search by continuous-time quantum walk. Phys. Rev. Lett. 129, 160502 (2022)MathSciNetCrossRefADS

25.

Roget, M., Kadri, H., Di Molfetta, G.: Optimality conditions for spatial search with multiple marked vertices. Phys. Rev. Res. 5, 033021 (2023)CrossRef

26.

Colbourne, C., Dinitz, J.: Handbook of Combinatorial Designs. CRC Press, Boca Raton (2007)

27.

Chakraborty, S., Novo, L., Roland, J.: Optimality of spatial search via continuous-time quantum walks. Phys. Rev. A 102, 032214 (2020)MathSciNetCrossRefADS

28.

Chan, A., Godsil, C.D., Tamon, C., Xie, W.: Of shadows and gaps in spatial search. Quantum Inf. Comput. 22(13 &14), 1110–1131 (2022)MathSciNet

29.

Teixeira da Silva, C.F., Posner, D., Portugal, R.: Walking on vertices and edges by continuous-time quantum walk. Quantum Inf. Process. 22(2), 93 (2023)MathSciNetCrossRefADS

30.

Portugal, R., Moqadam, J.K.: Implementation of continuous-time quantum walks on quantum computers. arXiv:2212.08889 (2022)

31.

Chen, Q.: PhD thesis, University of Waterloo, in preparation

Titel: Quantum search by continuous-time quantum walk on t-designs
verfasst von: Pedro H. G. Lugão
Renato Portugal
Publikationsdatum: 01.04.2024
Verlag: Springer US
Erschienen in: Quantum Information Processing / Ausgabe 4/2024
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-024-04355-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2024

Enhanced quantum transport in chiral quantum walks

Bidirectional quantum operation teleportation with two four-qubit cluster states

Toffoli-depth reduction method preserving in-place quantum circuits and its application to SHA3-256

Depth–measurement trade-off for quantum search on block ciphers

Entanglement entropy in a certain nonlinear discrete quantum walk model

Entropically secure encryption with faster key expansion