{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T13:05:50Z","timestamp":1774098350528,"version":"3.50.1"},"reference-count":78,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"Sydney Quantum Academy"},{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science and Technology","doi-asserted-by":"publisher","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X026167\/1"],"award-info":[{"award-number":["EP\/X026167\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,10,31]]},"DOI":"10.1137\/24m1638616","type":"journal-article","created":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:25:53Z","timestamp":1760081153000},"page":"1294-1334","source":"Crossref","is-referenced-by-count":2,"title":["Quantum Lower Bounds by Sample-to-Query Lifting"],"prefix":"10.1137","volume":"54","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5107-8279","authenticated-orcid":true,"given":"Qisheng","family":"Wang","sequence":"first","affiliation":[{"name":"School of Informatics, University of Edinburgh, Edinburgh, United Kingdom."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7436-0426","authenticated-orcid":true,"given":"Zhicheng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia."}]}],"member":"351","published-online":{"date-parts":[[2025,10,10]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.020"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.26421\/QIC12.1-2-3"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3015235"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1826"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.006"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/130939043"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3106234"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1364\/AOP.1.000238"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"ref18","first-page":"670","volume":"12","author":"Beame P.","year":"2012","journal-title":"Quantum Inform. Comput."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a003"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0150-x"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.042313"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3150-8"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2134250"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a010"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00190-7"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1080\/00107510010002599"},{"key":"ref45","first-page":"669","volume":"10","author":"Childs A. M.","year":"2010","journal-title":"Quantum Inform. Comput."},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"ref47","first-page":"901","volume":"12","author":"Childs A. M.","year":"2012","journal-title":"Quantum Inform. Comput."},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(75)90075-0"},{"key":"ref49","first-page":"41","volume":"17","author":"Chowdhury A. N.","year":"2017","journal-title":"Quantum Inform. Comput."},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.040303"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1137\/050644719"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/18.761271"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-022-00232-7"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ae075b"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1137\/16M1059369"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1137\/17M115339X"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/3589986"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.107.210501"},{"key":"ref74","first-page":"254","volume":"10","author":"Helstrom C. W.","year":"1967","journal-title":"Inform. Comput."},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(73)90028-6"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1016\/0034-4877(72)90011-0"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2641-8"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-017-0013-7"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2883306"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-12-14-372"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-025-00973-7"},{"key":"ref84","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-025-00273-8"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1126\/science.273.5278.1073"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1038\/nphys3029"},{"key":"ref90","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"ref98","series-title":"Graduate Surveys 7","first-page":"1","volume-title":"Theory of Computing Library","author":"Montanaro A.","year":"2016"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04180-1"},{"key":"ref102","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.220502"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a013"},{"key":"ref106","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.108.012409"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1137\/16M1064477"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a001"},{"key":"ref114","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.104.022428"},{"key":"ref116","doi-asserted-by":"publisher","DOI":"10.1038\/nature09770"},{"key":"ref119","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-14-230"},{"key":"ref120","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.052328"},{"key":"ref121","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3447915"},{"key":"ref122","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3399014"},{"key":"ref124","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3321121"},{"key":"ref125","author":"Wang Q.","year":"2025","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref126","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3203985"},{"key":"ref127","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3382037"},{"key":"ref129","doi-asserted-by":"publisher","DOI":"10.22331\/q-2025-04-18-1717"},{"key":"ref130","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139525343"},{"key":"ref131","doi-asserted-by":"publisher","DOI":"10.1016\/j.aop.2011.06.001"},{"key":"ref132","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1111758109"},{"key":"ref133","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.60.2746"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:25:55Z","timestamp":1760081155000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1638616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,10]]},"references-count":78,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1137\/24M1638616"],"URL":"https:\/\/doi.org\/10.1137\/24m1638616","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,10]]}}}