{"entities":{"Q3068642":{"pageid":3079358,"ns":120,"title":"Item:Q3068642","lastrevid":51165419,"modified":"2026-01-17T00:58:23Z","type":"item","id":"Q3068642","labels":{"en":{"language":"en","value":"Any AND-OR formula of size \\(N\\) can be evaluated in time \\(N^{1/2+o(1)}\\) on a quantum computer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5837598"}},"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":"Q3068642$0D0F1C8B-AAFC-4083-B100-54A38C1C6948","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b086225428680e712cf1227e3c1083954a5c4da3","datavalue":{"value":{"text":"Any AND-OR Formula of Size <i>N</i> Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3068642$BF4168C3-3583-47F9-9C03-F90B07EC4CBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"84d77185aa4833cbe95bc5d4fd8326a50d757440","datavalue":{"value":"1207.68151","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$CFA82EE6-3384-44D1-946D-71874727EC86","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4b390ae993f344dfe7838ecfab214ae1592748bf","datavalue":{"value":"10.1137/080712167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$6F4A14E3-6B0B-4318-87A1-0672D7148A38","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"26dc40e72e01259ac24f74ac0a889f1065c2be93","datavalue":{"value":{"entity-type":"item","numeric-id":380045,"id":"Q380045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$CCC03FE8-DD5D-40F4-AFED-D14129E2EF38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"334333edb48dc65bd7aa9d5838c874ddfc1fa9f7","datavalue":{"value":{"entity-type":"item","numeric-id":616870,"id":"Q616870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$D4DE06D2-50BA-487B-B6B2-80561B0B3E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"134d8db8cf7bce6f6dce986dfa74f96fd075b6d7","datavalue":{"value":{"entity-type":"item","numeric-id":835641,"id":"Q835641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$F4E1A578-7865-4390-8164-333BF2E4816B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71cc9c31d63659d2a0be47fa8206a760572b719a","datavalue":{"value":{"entity-type":"item","numeric-id":496890,"id":"Q496890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$03A05A0F-5C61-4F6E-BF9D-FBB57E69FED8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9612c4adae3ffe2578a5e7a91ff6304cb5e074b","datavalue":{"value":{"entity-type":"item","numeric-id":230552,"id":"Q230552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$930AE973-B3E1-4C20-B87E-1DB162B8EF62","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3068642$050F81C2-83E3-4BAF-929B-B8B09925ED35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0883ac07d245f1112570cf26b29891637a99bfe6","datavalue":{"value":{"time":"+2011-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3068642$79B08F3F-F228-40B0-BCBB-26BF361944ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d49e87838bc3cca1b2ca46cd3cc36550e9683434","datavalue":{"value":"68Q12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$50D772C7-C17F-421B-94F0-743D558061D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$89306165-D1E8-4F47-8CAF-6E64862B2A7D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f9d388f8039a74a1b9cbd3b820c500981c9a68b","datavalue":{"value":"5837598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$F6E0C298-F5C2-48C1-BD43-97DF8D3D749E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd0a85fc687d5a2030ca309942325a5872eec67b","datavalue":{"value":"quantum computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3068642$E8CD40CE-BCAE-4162-BF54-75DB0A8D2D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a8cbbdeb5f77c4a960dd4bfd839e8a4c245b528","datavalue":{"value":"quantum query complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3068642$8C08F75C-5647-437D-97D7-B4142F7F54E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dabb361caf7ef0ad35107377abbba4355a741a62","datavalue":{"value":"formula evaluation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3068642$A6C67989-69D7-49E5-939F-2464B9F5216F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ad71a1ffaf268b8c177d1fefd925d2ecb68c875","datavalue":{"value":"AND-OR trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q3068642$7D2FE770-17DB-401A-9F82-6D2A5A620A11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c152a0018dc452ac0f1906d815946b10e4ad6d0b","datavalue":{"value":"quantum walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q3068642$8CB751E9-1EF8-4CCC-8305-CBDC9E43D638","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":"Q3068642$B56B10D6-CB6D-4243-8AC4-02FB38551450","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c89084d6ec37f9f3837f2947723a6a9cd359f91","datavalue":{"value":"https://doi.org/10.1137/080712167","type":"string"},"datatype":"url"},"type":"statement","id":"Q3068642$FBBBFFC1-12B7-449A-8EA2-42D9E9C52E98","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"894f08733850fc38b691663ba5d23f0b3c3f408f","datavalue":{"value":"W2031374990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3068642$FFDA2955-C8F2-410C-8A37-ECFB3B9970A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e19af8d4bf0e091a90cbab9d4022634a2d999944","datavalue":{"value":{"entity-type":"item","numeric-id":3453313,"id":"Q3453313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac9a17ab487ed1d2019e92de810a75c24f79aab8","datavalue":{"value":{"amount":"+0.8345284461975098","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3068642$E6155F25-C00E-4399-B776-B5FC0CF23971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0364d534f4d15899e4398545f3c34f7f8dd40ed","datavalue":{"value":{"entity-type":"item","numeric-id":2912853,"id":"Q2912853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"788d07baaac57f4d8e687e1478b432f01056e3de","datavalue":{"value":{"amount":"+0.8196173310279846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3068642$E071420C-56CF-4CCB-9B94-0825128E335C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"733dec35d7d54e4255aaaff55f5d9cf20b499e52","datavalue":{"value":{"entity-type":"item","numeric-id":5365062,"id":"Q5365062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"667e0a281ab5ab0dc8e625205ad59c2fce7d89c1","datavalue":{"value":{"amount":"+0.8189198970794678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3068642$A969B5CC-F1EB-430F-B2BE-B7B82449C412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e7d5052797b89be897248bd444c7743b30eecfb","datavalue":{"value":{"entity-type":"item","numeric-id":2913813,"id":"Q2913813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2fb71a6d002cd6785cb54097d1b70a8a5bf16b8","datavalue":{"value":{"amount":"+0.8024470210075378","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3068642$DFF4F1A9-C637-4424-AEB5-8D3F3032F417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14aa3988e8e344d27a146c608e287963c9bafdb1","datavalue":{"value":{"entity-type":"item","numeric-id":2826061,"id":"Q2826061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef3cba87b5503645df87260fce102c3da8213a35","datavalue":{"value":{"amount":"+0.7992520928382874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3068642$70A97AC4-99C0-4B84-B269-D54538FED594","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3068642","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3068642"}}}}}