{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T21:26:39Z","timestamp":1785014799581,"version":"3.55.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            It has recently been shown that starting with a classical query algorithm (decision tree) and a guessing algorithm that tries to predict the query answers, we can design a quantum algorithm with query complexity\n            <jats:italic>O(<\/jats:italic>\n            \u221a\n            <jats:italic>GT<\/jats:italic>\n            where\n            <jats:italic>T<\/jats:italic>\n            is the query complexity of the classical algorithm (depth of the decision tree) and\n            <jats:italic>G<\/jats:italic>\n            is the maximum number of wrong answers by the guessing algorithm\u00a0[\n            <jats:xref ref-type=\"bibr\">3<\/jats:xref>\n            ,\n            <jats:xref ref-type=\"bibr\">14<\/jats:xref>\n            ]. In this article, we show that, given some constraints on the classical algorithms, this quantum algorithm can be implemented in time\n            <jats:italic>O\u0303<\/jats:italic>\n            (\u221a\n            <jats:italic>GT<\/jats:italic>\n            ). Our algorithm is based on non-binary span programs and their efficient implementation. We conclude that various graph-theoretic problems including bipartiteness, cycle detection, and topological sort can be solved in time\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) and with\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) quantum queries. Moreover, finding a maximal matching can be solved with\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) quantum queries in time\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), and maximum bipartite matching can be solved in time\n            <jats:italic>O(n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3519269","type":"journal-article","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T11:54:30Z","timestamp":1648468470000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Time- and Query-optimal Quantum Algorithms Based on Decision Trees"],"prefix":"10.1145","volume":"3","author":[{"given":"Salman","family":"Beigi","sequence":"first","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1723-9144","authenticated-orcid":false,"given":"Leila","family":"Taghavi","sequence":"additional","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Artin","family":"Tajdini","sequence":"additional","affiliation":[{"name":"QuOne Lab, Phanous Research and Innovation Centre, Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_13"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.26421\/QIC19.9-10"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-03-02-241"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_18"},{"key":"e_1_3_3_6_2","article-title":"Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness","author":"Cade Chris","year":"2016","unstructured":"Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. 2016. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. arXiv:1610.00581 (Oct. 2016).","journal-title":"arXiv:1610.00581"},{"key":"e_1_3_3_7_2","unstructured":"Arjan Cornelissen Stacey Jeffery Maris Ozols and Alvaro Piedrafita. 2020. Span programs and quantum time complexity. Retrieved from https:\/\/scirate.com\/arxiv\/2005.01323."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9118-x"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/050644719"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.12"},{"key":"e_1_3_3_12_2","article-title":"A query-efficient quantum algorithm for maximum matching on general graphs","author":"Kimmel Shelby","year":"2020","unstructured":"Shelby Kimmel and R. Teal Witter. 2020. A query-efficient quantum algorithm for maximum matching on general graphs. arXiv preprint arXiv:2010.02324. (2020).","journal-title":"arXiv preprint arXiv:2010.02324."},{"key":"e_1_3_3_13_2","unstructured":"Alexey Yu. Kitaev. 1995. Quantum measurements and the Abelian stabilizer problem. arxiv:quant-ph\/9511026"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.75"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a018"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/1972505"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.55"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519269","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3519269"],"URL":"https:\/\/doi.org\/10.1145\/3519269","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,27]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}