{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:01Z","timestamp":1740137221840,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T00:00:00Z","timestamp":1624406400000},"content-version":"vor","delay-in-days":22,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"MINECO","award":["MTM-2017- 83506-C2-2-P","MINECO-16-TEC2015-67387-C4-3-R"],"award-info":[{"award-number":["MTM-2017- 83506-C2-2-P","MINECO-16-TEC2015-67387-C4-3-R"]}]},{"DOI":"10.13039\/501100004837","name":"MICINN","doi-asserted-by":"crossref","award":["RTI2018-098085-B-C44","FC-GRUPIN- IDI\/2018\/000193"],"award-info":[{"award-number":["RTI2018-098085-B-C44","FC-GRUPIN- IDI\/2018\/000193"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004837","name":"MICINN","doi-asserted-by":"crossref","award":["FC-GRUPIN-IDI\/2018\/000226"],"award-info":[{"award-number":["FC-GRUPIN-IDI\/2018\/000226"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Two of the most well-known quantum algorithms, those introduced by Deutsch\u2013Jozsa and Bernstein\u2013Vazirani, can solve promise problems with just one function query, showing an oracular separation with deterministic classical algorithms. In this work, we generalise those methods to study a family of quantum algorithms that can, with just one query, exactly solve promise problems stated over Boolean functions. We also show that these problems can be naturally ordered, inducing a partially ordered set of promise problems. We study the properties of such a poset, showing that the Deutsch\u2013Jozsa and Bernstein\u2013Vazirani problems are, in a certain sense, extremal problems in it, determining some of its automorphisms and proving that it is connected. We also prove that, for the problems in the poset, the corresponding classical query complexities can take any value between 1 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{n-1}+1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mrow>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s11128-021-03156-3","type":"journal-article","created":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T08:02:58Z","timestamp":1624435378000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On a poset of quantum exact promise problems"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3808-4273","authenticated-orcid":false,"given":"El\u00edas F.","family":"Combarro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofia","family":"Vallecorsa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto Di","family":"Meglio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"Pi\u00f1era","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignacio Fern\u00e1ndez","family":"R\u00faa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,23]]},"reference":[{"issue":"5","key":"3156_CR1","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput. 26(5), 1411\u20131473 (1997). https:\/\/doi.org\/10.1137\/S0097539796300921","journal-title":"SIAM J. Comput."},{"key":"3156_CR2","doi-asserted-by":"crossref","unstructured":"Combarro, E.F., Carminati, F., Vallecorsa, S., Ranilla, J., R\u00faa, I.F.: On protocols for increasing the uniformity of random bits generated with noisy quantum computers. J. Supercomput. (2021) in press","DOI":"10.1007\/s11227-020-03574-7"},{"key":"3156_CR3","doi-asserted-by":"crossref","unstructured":"Combarro, E.F., Pi\u00f1era Nicol\u00e1s, A., Ranilla, J., R\u00faa, I.F.: An explanation of the Bernstein\u2013Vazirani and Deustch\u2013Josza algorithms with the quantum stabilizer formalism. Comput. Math. Methods e1120 (2020)","DOI":"10.1002\/cmm4.1120"},{"key":"3156_CR4","doi-asserted-by":"publisher","first-page":"45554","DOI":"10.1109\/ACCESS.2019.2908785","volume":"7","author":"EF Combarro","year":"2019","unstructured":"Combarro, E.F., Ranilla, J., R\u00faa, I.F.: A quantum algorithm for the commutativity of finite dimensional algebras. IEEE Access 7, 45554\u201345562 (2019)","journal-title":"IEEE Access"},{"key":"3156_CR5","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.cam.2018.09.050","volume":"354","author":"EF Combarro","year":"2019","unstructured":"Combarro, E.F., Ranilla, J., R\u00faa, I.F.: Quantum walks for the determination of commutativity of finite dimensional algebras. J. Comput. Appl. Math. 354, 496\u2013506 (2019)","journal-title":"J. Comput. Appl. Math."},{"key":"3156_CR6","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/s11128-020-02763-w","volume":"19","author":"EF Combarro","year":"2020","unstructured":"Combarro, E.F., Ranilla, J., R\u00faa, I.F.: Quantum abstract detecting systems. Quantum Inf. Process. 19, 258 (2020)","journal-title":"Quantum Inf. Process."},{"key":"3156_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church\u2013Turing principle and the universal quantum computer. Proc. R. Soc. Lond. Ser. A 400, 97\u2013117 (1985)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"issue":"1907","key":"3156_CR8","first-page":"553","volume":"439","author":"D Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. 439(1907), 553\u2013558 (1992)","journal-title":"Proc. R. Soc. Lond. A Math. Phys. Eng. Sci."},{"issue":"6","key":"3156_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R Feynman","year":"1982","unstructured":"Feynman, R.: Simulating physics with computers. Int. J. Theor. Phys. 21(6), 467\u2013488 (1982)","journal-title":"Int. J. Theor. Phys."},{"key":"3156_CR10","doi-asserted-by":"publisher","first-page":"1918","DOI":"10.1038\/s41467-017-01904-7","volume":"8","author":"C Figgatt","year":"2017","unstructured":"Figgatt, C., Maslov, D., Landsman, K.A., et al.: Complete 3-Qubit Grover search on a programmable quantum computer. Nat. Commun. 8, 1918 (2017)","journal-title":"Nat. Commun."},{"key":"3156_CR11","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC \u201996, pp. 212\u2013219. ACM, New York, NY, USA (1996)","DOI":"10.1145\/237814.237866"},{"key":"3156_CR12","unstructured":"IBM Quantum (2021). https:\/\/quantum-computing.ibm.com\/"},{"key":"3156_CR13","unstructured":"Kitaev, A.Y.: Quantum measurements and the abelian stabilizer problem. Electron. Colloq. Comput. Complex.: ECCC 3 (1995)"},{"key":"3156_CR14","unstructured":"Manin, Y.: Vychislimoe i nevychislimoe. Sov. Radio, pp. 13\u201315 (1980)"},{"key":"3156_CR15","volume-title":"Quantum Computation and Quantum Information: 10th Anniversary","author":"MA Nielsen","year":"2011","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary. Cambridge University Press, Cambridge (2011)"},{"issue":"11","key":"3156_CR16","doi-asserted-by":"publisher","first-page":"4461","DOI":"10.1007\/s11128-016-1427-4","volume":"15","author":"RAM Santos","year":"2016","unstructured":"Santos, R.A.M.: Szegedy\u2019s quantum walk with queries. Quantum Inf. Process. 15(11), 4461\u20134475 (2016)","journal-title":"Quantum Inf. Process."},{"key":"3156_CR17","unstructured":"Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of FOCS, pp. 124\u2013134 (1994)"},{"key":"3156_CR18","doi-asserted-by":"crossref","unstructured":"Simon, D.R.: On the power of quantum computation. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS \u201994, pp. 116\u2013123. IEEE Computer Society, USA (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365701","DOI":"10.1109\/SFCS.1994.365701"},{"key":"3156_CR19","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201904, pp. 32\u201341. IEEE Computer Society, Washington, DC, USA (2004)"},{"key":"3156_CR20","doi-asserted-by":"crossref","unstructured":"Wong, T.: Faster search by lackadaisical quantum walk. Quantum Inf. Process. 17(68) (2018)","DOI":"10.1007\/s11128-018-1840-y"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03156-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03156-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03156-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T09:23:32Z","timestamp":1635240212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03156-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["3156"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03156-3","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2021,6]]},"assertion":[{"value":"6 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The funding note information has been added in the article.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"214"}}