{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:34Z","timestamp":1781077954048,"version":"3.54.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T00:00:00Z","timestamp":1661904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"National Science Foundation","award":["CCF-1412958, and CCF-1763311"],"award-info":[{"award-number":["CCF-1412958, and CCF-1763311"]}]},{"name":"Motwani Postdoctoral Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n            We present a distribution \ud835\udcd3 over inputs in {\u00b1 1}\n            <jats:sup>\n              2\n              <jats:italic>N<\/jats:italic>\n            <\/jats:sup>\n            , such that:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>\n                  There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time\n                  <jats:italic>O<\/jats:italic>\n                  (log\n                  <jats:italic>N<\/jats:italic>\n                  ), that distinguishes between \ud835\udcd3 and the uniform distribution with advantage\n                  <jats:italic>\u03a9<\/jats:italic>\n                  (1\/log\n                  <jats:italic>N<\/jats:italic>\n                  ).\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>\n                  No Boolean circuit of quasi-polynomial size and constant depth distinguishes between \ud835\udcd3 and the uniform distribution with advantage better than polylog(N)\/\u221a\n                  <jats:italic>N<\/jats:italic>\n                  .\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            By well-known reductions, this gives a separation of the classes Promise-\n            <jats:bold>BQP<\/jats:bold>\n            and Promise-\n            <jats:bold>PH<\/jats:bold>\n            in the\n            <jats:italic>black-box<\/jats:italic>\n            model and implies an oracle relative to which\n            <jats:bold>BQP<\/jats:bold>\n            is not contained in\n            <jats:bold>PH<\/jats:bold>\n            .\n          <\/jats:p>","DOI":"10.1145\/3530258","type":"journal-article","created":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T11:16:56Z","timestamp":1651663016000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Oracle Separation of BQP and PH"],"prefix":"10.1145","volume":"69","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,8,31]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_4_4_2","doi-asserted-by":"crossref","unstructured":"Daniel R. Simon. 1997. On the power of quantum computation. SIAM Journal on Computing 26 5 (1997) 1474\u20131483.","DOI":"10.1137\/S0097539796298637"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892141"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050902"},{"key":"e_1_3_4_9_2","unstructured":"Lijie Chen. 2016. A note on oracle separations for BQP. arXiv:1605.00619. Retrieved from https:\/\/arxiv.org\/abs\/1605.00619."},{"key":"e_1_3_4_10_2","unstructured":"Scott Aaronson. 2011. A counterexample to the generalized linial-nisan conjecture. arXiv:1110.6126. Retrieved from https:\/\/arxiv.org\/abs\/1110.6126."},{"key":"e_1_3_4_11_2","doi-asserted-by":"crossref","unstructured":"Bill Fefferman Ronen Shaltiel Christopher Umans and Emanuele Viola. 2013. On beating the hybrid argument. Theory and Computation 9 Article 26 (2013) 809\u2013843.","DOI":"10.4086\/toc.2013.v009a026"},{"key":"e_1_3_4_12_2","doi-asserted-by":"crossref","unstructured":"Zachary Remscrim. 2016. The hilbert function algebraic extractors and recursive fourier sampling. In Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science . IEEE Computer Society 197\u2013208.","DOI":"10.1109\/FOCS.2016.29"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_4_14_2","first-page":"15:1\u201315:31","volume-title":"Proceedings of the Computational Complexity Conference","author":"Tal Avishay","year":"2017","unstructured":"Avishay Tal. 2017. Tight bounds on the fourier spectrum of AC0. In Proceedings of the Computational Complexity Conference. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:31."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/120897432"},{"key":"e_1_3_4_17_2","first-page":"1:1\u20131:21","volume-title":"Proceedings of the Computational Complexity Conference","author":"Chattopadhyay Eshan","year":"2018","unstructured":"Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. 2018. Pseudorandom generators from polarizing random walks. In Proceedings of the Computational Complexity Conference. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 1:1\u20131:21."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.2307\/2331932"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530258","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:24Z","timestamp":1750183764000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,31]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3530258"],"URL":"https:\/\/doi.org\/10.1145\/3530258","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,31]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}