{"entities":{"Q433109":{"pageid":434876,"ns":120,"title":"Item:Q433109","lastrevid":38346832,"modified":"2024-12-09T16:25:52Z","type":"item","id":"Q433109","labels":{"en":{"language":"en","value":"On the uselessness of quantum queries"}},"descriptions":{"en":{"language":"en","value":"scientific article"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$C977A5A6-798A-4A7F-97BD-9DB32C18D817","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"69b0a2ba9a6dbbc0d3865f5eb0d51ff47e0043d4","datavalue":{"value":{"text":"On the uselessness of quantum queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q433109$389FFE12-198B-43A1-B772-6771420F8E95","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28bf563f9860614e0aa44136d6fb81c39b261dcc","datavalue":{"value":"1267.68116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$1601FC26-963B-4948-8024-9565D91965C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0919852595f432ec71efc972cc3a2ce3a1daa6a8","datavalue":{"value":{"entity-type":"item","numeric-id":207878,"id":"Q207878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$2CA71542-7219-4D2F-BF27-44583DBDC149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f3ab86a17b5ebd9a64987482ffaa190b2233c6a","datavalue":{"value":{"entity-type":"item","numeric-id":1318044,"id":"Q1318044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$CD5B5387-B7F9-479B-92FA-EAFFE24A2FD3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$F8AAA515-DD56-4865-BF5D-27992DEF24DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b8169782b0c1573ab69940e37078f3a0c71cae46","datavalue":{"value":{"time":"+2012-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q433109$73F170F3-1613-41E9-A90B-85FD7242AF04","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb28e9821f178598be18852829622d4234159209","datavalue":{"value":"The paper treats the classical and quantum query complexity of oracles. These provide the values of an unknown function in response to queries and the task is to determine a property of the function. In the introduction, some easy-to-follow examples of useful and useless queries are presented. Afterwards, classical ``uselessness'' of \\(k\\) queries to the oracle is strictly defined: Knowledge of any \\(k\\) function values does not change the probability of the function to belong to a particular property class. The quantum generalization is straightforward: \\(k\\) quantum queries are useless if afterwards no measurement (described by a generalized POVM) changes the probability of the function to have the sought-after property. For example, in Deutsch's problem, a single classical query is useless whereas a single quantum query may be useful.  The main result of the paper is that when \\(2k\\) classical queries are useless, also \\(k\\) quantum queries are, which gives a lower bound to useful quantum queries as \\(k+1\\). The paper provides three examples (a parity problem, a generalization of Deutsch's problem, and a polynomial interpolation problem) and of course the proof of the main theorem. The authors suggest to use their theorem for obtaining a lower bound of quantum query complexities. Although a bit technical, the paper is easy to read and recommendable for researchers interested in quantum query complexity with background in quantum algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q433109$F0385C66-7D57-4231-99CE-771078B7DC79","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"738b8b7c7ebc83d2577988148f54a03ddb1aafc8","datavalue":{"value":{"entity-type":"item","numeric-id":590950,"id":"Q590950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$DD1541F2-6143-4521-8B22-B2F4591E5395","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d49e87838bc3cca1b2ca46cd3cc36550e9683434","datavalue":{"value":"68Q12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$5A202677-3856-4AED-AEA6-3BDD4F463FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$EC126CDC-D4ED-46A0-BAA7-4507EA3E8698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$6A76AE6D-57EC-46EC-AD91-AEF9AFA58D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$8C741C6C-5DE5-4A60-A940-5C5110331286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5ba4f254528f0243a639e5d75d2711104b8610ab","datavalue":{"value":"81P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$690BEA7B-DD18-4112-B85B-A6521AF1EAE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aa260079cfd52a91c46affe4c48842afa1d09092","datavalue":{"value":"6055702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$9EC08293-F960-4654-A3FC-3AE6C7CB91AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"824fc69ab36980fdea1164fe82e1a760c1b55b4c","datavalue":{"value":"quantum algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q433109$0A638D09-F3DE-4F06-B651-49BEFAC4384D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca97feacc9e65d2caecf2614279d5649c5d7a6df","datavalue":{"value":"oracle query complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q433109$68A710FF-0034-4532-8E56-8D4A6ACE44EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q433109$ED82F776-A4D4-46F7-9717-88671ED4CF5C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$1A435276-6CD2-4460-86EC-E05852D06276","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"39b2566ec74e91a02c729503ebafd11fb5b014a7","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.06.037","type":"string"},"datatype":"url"},"type":"statement","id":"Q433109$0B9A7723-2A0D-45B7-91E0-AE02A21EBF21","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2739cd21388b6572c96d717925f35ec5f3149edd","datavalue":{"value":"W1870507853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$0DC8959B-2668-44DE-A8E5-A7F18FC4542F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf854375ef6a956c526c0de5e533214f6344181a","datavalue":{"value":{"entity-type":"item","numeric-id":4376181,"id":"Q4376181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$6AF9D3C2-2018-43BF-BA6B-27A289D20350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c982cbb5e59dc7e2ae30800c6f4d626a4d47b8","datavalue":{"value":{"entity-type":"item","numeric-id":4376179,"id":"Q4376179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$D059FACF-49FB-4F96-9DB8-25A444A97AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4375904b8aa076055dd42498948d54f6a1b282ad","datavalue":{"value":{"entity-type":"item","numeric-id":4343414,"id":"Q4343414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$A0937BAF-047D-4478-818B-CC7854BDECD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4147c269b4cb3c44889750377eaa18e88ef2bbb","datavalue":{"value":{"entity-type":"item","numeric-id":4223936,"id":"Q4223936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$05F7FA3D-F67E-4BA8-97EA-8DF169A92A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33df3bbf37d10172a73ff9a6acfca59785e91505","datavalue":{"value":{"entity-type":"item","numeric-id":4212472,"id":"Q4212472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$BD4B4D6C-418A-46D3-B082-70F4FDABFE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6174131b15465b67943b65012f53c599ead6e298","datavalue":{"value":{"entity-type":"item","numeric-id":4223937,"id":"Q4223937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$CD5682BA-CA38-412C-B293-40318F7477C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c81ee2ca0256eec06c7cc1d6395ec3f796ec9064","datavalue":{"value":{"entity-type":"item","numeric-id":5441359,"id":"Q5441359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$DC3BCA5D-243A-4E46-A86D-63AD37006BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4ee54ec11d06e8a5c8eab19f2efedb4f4c5160d","datavalue":{"value":{"entity-type":"item","numeric-id":3050283,"id":"Q3050283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$86DEBA48-1740-42A8-926A-9D0AE578085B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4e27f6918ccba403217a4d22eacb3da1fc444ca","datavalue":{"value":{"entity-type":"item","numeric-id":3171628,"id":"Q3171628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$B3CD00EF-ED04-4452-867C-32EA6361F7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"823e2611d01d15181e54e23477e000d29a5a124d","datavalue":{"value":{"entity-type":"item","numeric-id":5414589,"id":"Q5414589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$652CBEF2-F89A-49DB-9CB7-CADCDE351FE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"764b9de4a0853139f070b139138edffdffe3b436","datavalue":{"value":{"entity-type":"item","numeric-id":3597890,"id":"Q3597890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$64CA4801-F77D-40A6-9AB2-36F1128C6039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a810594d643624f2a58bf02bb43f6aa851f4f30c","datavalue":{"value":{"entity-type":"item","numeric-id":989901,"id":"Q989901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$B1B28D0E-6489-43DF-A336-A8E94DDA2201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c3d281ab1020686fa49be9fbda50f89b24139f2","datavalue":{"value":{"entity-type":"item","numeric-id":2232294,"id":"Q2232294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$06E8E215-1BE7-429D-8428-865FC9B6A1FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c1b03f18d24853b4b5c9105a4bf170c993c5f94","datavalue":{"value":{"entity-type":"item","numeric-id":4542520,"id":"Q4542520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$3E1CD00B-9C73-43FF-8E7F-ED5FC58B90F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176b368822d249ecb31cec25034aa2d09baad3ae","datavalue":{"value":{"entity-type":"item","numeric-id":4819589,"id":"Q4819589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q433109$DFE69903-8FEB-4534-90BC-56C68D7627A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1895574bc3dc391a487555a0be3decb4a3d0b25c","datavalue":{"value":"10.1016/J.TCS.2011.06.037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q433109$55B39323-909D-4FF2-9539-1BDDC3E64B72","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:433109","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:433109"}}}}}