{"entities":{"Q2462663":{"pageid":2473406,"ns":120,"title":"Item:Q2462663","lastrevid":57938955,"modified":"2026-04-03T04:15:24Z","type":"item","id":"Q2462663","labels":{"en":{"language":"en","value":"Quantum algorithms for learning and testing juntas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5217119"}},"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":"Q2462663$C6ECE0E3-AE55-450E-9ECF-DE57CFE5F03D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"050c3b40c3ad4c4117db8da10cb438ed35309881","datavalue":{"value":{"text":"Quantum algorithms for learning and testing juntas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2462663$CFB68A1E-638D-47A4-97D2-19A4BFFEEB74","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cdbbc302a83fdce7a95bcc742ba9fe133dbf3b61","datavalue":{"value":"1155.81014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$D0D0C625-20EC-45CE-A3C5-0E6D40BC79A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7f6de71f5402c26bbc2b68e99d3d9a14013f8ef","datavalue":{"value":{"entity-type":"item","numeric-id":950196,"id":"Q950196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$C42C77BE-8495-4C69-828A-37214FE0B82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2be8fb6e35685e07f3610c2a477e3fd665571740","datavalue":{"value":{"entity-type":"item","numeric-id":371199,"id":"Q371199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$07A982B9-09E4-4C43-B98B-88B4409279F4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7a35f561d0936669a320f067afb4f0e42f9e2f53","datavalue":{"value":{"entity-type":"item","numeric-id":264592,"id":"Q264592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$5FF20317-5047-403F-96AC-0C207DB54068","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9fa6f2f337ef8352aec632547ae6f1ca832f426","datavalue":{"value":{"time":"+2007-12-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2462663$CBD4B1AD-2E2B-4F9F-B2B4-46BC4F19AECE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"930c99d1ba5e3dbeed753738dc771e2c8328756d","datavalue":{"value":"https://arxiv.org/abs/0707.3479","type":"string"},"datatype":"url"},"type":"statement","id":"Q2462663$EE9ADA9B-3B5A-4FD9-871E-57D0BFF047C2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"86562c67951051a76fc4db07c78df3d95ca28fea","datavalue":{"value":"This article considers quantum algorithms for testing and learning juntas, i.e.\\ Boolean functions depending only on unknown sets of \\(k\\) out of \\(n\\) input variables. It introduces, and proves nearly optimal, a junta-learning algorithm with sample complexity independent of \\(n\\) requiring neither classical nor quantum membership (``black-box'') queries. Instead, to achieve a fixed accuracy, the algorithm requires only \\(O(2^k)\\) uniformly random classical examples together with \\(O(k\\log k)\\) ``Fourier samples.'' (A Fourier sample produces a subset of \\(\\{1, \\ldots, n\\}\\) drawn according to the unknown function's Fourier spectrum; it can be implemented on a quantum computer but is weaker than a quantum membership query.) Also introduced is a junta-testing algorithm with Fourier sample complexity linear in \\(k\\) for fixed accuracy; this improves on the best known classical membership query complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$500EF159-5716-4D25-858C-234B87D35573","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$AF6CB284-8D45-449E-91F3-2234C164E8AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$BE3C6301-7E22-4577-B29E-D045E4AB70DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4ca6466a7922f60bdab93734576433639102238c","datavalue":{"value":"5217119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$487C6CBF-8D7E-4503-9D95-0AFB3250AC1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3d30e58cbda622b3b9716f759932eda5d7effaa","datavalue":{"value":"junta","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$9C35F004-0ED2-4139-8D1E-2A4429F7287D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"165e01f5c9f23365c83d4a235bf0332f5faa5373","datavalue":{"value":"quantum algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$E6FC6E2D-FFB7-447B-8D20-00FB7F2DA0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8bcf80a19ca5bc312a3de01f6709819ff6e0c9c","datavalue":{"value":"quantum property testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$6E885484-0A99-449D-B00E-E77F5011E668","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"81a56cecd4c580bb9e8a640d3f487f2f064f44f0","datavalue":{"value":"computational learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$67C045C6-7681-477C-9DB2-B0718923580A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2313a80f7dab0815c622b74250919a579e6af146","datavalue":{"value":"Fourier sample","type":"string"},"datatype":"string"},"type":"statement","id":"Q2462663$56D6BBE1-EBD8-41C5-AF34-5F26DACE1C1C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"47f6ef3c83be43f23329d5be57b6106c5c7e0daf","datavalue":{"value":{"entity-type":"item","numeric-id":813360,"id":"Q813360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$B4BB3CA1-DC96-4C90-B540-1B03ACF6527D","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":"Q2462663$AD15919F-0E3E-4DF8-B159-EE8CED1CDDEF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08ef46a075ba27d07165c6f42d788e752920edd0","datavalue":{"value":"W3099022082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$93B446F7-B4D7-4017-844D-E9EB84755880","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf3bf07250debd89fcfe8d0b7c0c1360d9c43c9","datavalue":{"value":{"entity-type":"item","numeric-id":2491374,"id":"Q2491374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$AD3F87E8-8FEE-427A-B392-C55469F064F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3a85d99c5d6c1221ea66adba8d33278e17e6ac7","datavalue":{"value":{"entity-type":"item","numeric-id":4229427,"id":"Q4229427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$BEC9DDED-8FF2-43B7-B4BD-BA0646557B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9cced0008c01fe639b7eb9ea935d2d3e34ade95","datavalue":{"value":{"entity-type":"item","numeric-id":5757907,"id":"Q5757907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$AE21F3D5-3615-4AE9-9786-DBBAD7DDF187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"420e34afb9b572970d005f147c9e58438cdcefd5","datavalue":{"value":{"entity-type":"item","numeric-id":4651506,"id":"Q4651506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$CEC35102-3DFE-49FD-ABE3-9358967A8DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f96f21576238d75d110944f8f862df5a9207014","datavalue":{"value":{"entity-type":"item","numeric-id":5716755,"id":"Q5716755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$84B5F02D-6DF6-4264-BAD2-50DC269A9BBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d071c0e63ccc4acf5f859969db29f7f9386afa","datavalue":{"value":{"entity-type":"item","numeric-id":1384530,"id":"Q1384530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$1B71E2D7-91F3-42D1-8D5D-46BE4839E9CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9409771bdbff3e1e4c1924ab44e80456f13c66b","datavalue":{"value":{"entity-type":"item","numeric-id":5897381,"id":"Q5897381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$08EEF07E-CA04-404C-92D4-AD7102DC2B8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"247205245bfcf24ac6d2c644389636d96b744e22","datavalue":{"value":{"entity-type":"item","numeric-id":5898893,"id":"Q5898893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$077935DB-C18C-4FB8-A2BF-9B132807C26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b765e22e9f16ad27be279f840ea124471d5fe19d","datavalue":{"value":{"entity-type":"item","numeric-id":2390270,"id":"Q2390270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$1D40C735-F497-4C47-A977-45B22F06FA4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b819f6089b7481c8eabf8e6f52e20ece25cd034","datavalue":{"value":{"entity-type":"item","numeric-id":1886314,"id":"Q1886314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$E861061B-1BCD-47D5-853C-4799D384C701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93102dc9c5454b4e87e550298f9d68a170764862","datavalue":{"value":{"entity-type":"item","numeric-id":4839061,"id":"Q4839061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$B35708C7-633D-4A54-9A0F-9E7B8E59F4C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49172515abb1787109c970b5001f0a76a4d18de1","datavalue":{"value":{"entity-type":"item","numeric-id":4277547,"id":"Q4277547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$EB85E33D-BB4D-4F31-BAE3-4C24825122BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc39092484c42c2661962bc3a074cbc74d5b534e","datavalue":{"value":{"entity-type":"item","numeric-id":3158518,"id":"Q3158518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$27890038-255B-49AA-B4AB-7468B1FD56FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3af9c400472b33809e98a7c72843fa27c42a11de","datavalue":{"value":{"entity-type":"item","numeric-id":4877517,"id":"Q4877517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$E57AC6BD-C6F4-40B4-9F97-AF3D0BAD4CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b157b02484e4595fbaef25c02de6a19894a7dd7","datavalue":{"value":{"entity-type":"item","numeric-id":4376183,"id":"Q4376183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$F4992B2F-0F7F-4069-875C-C155E843D00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb8485af4f2dd4cfae0164b58f96a808b5d82c01","datavalue":{"value":{"entity-type":"item","numeric-id":1924380,"id":"Q1924380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2462663$774FD8D7-8D5D-4EC6-8774-306D8AB3AE50","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aad6b3de1ecce9b4e72bda3fe915eefad19c6190","datavalue":{"value":"10.1007/S11128-007-0061-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2462663$5A582BFC-19BA-4AB3-A7BE-14BB0F160658","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66336408c2928bd0b1711b18377478049316dcf","datavalue":{"value":{"entity-type":"item","numeric-id":2351390,"id":"Q2351390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13ef95a72974597e9f0105c4e885287de30bd1b1","datavalue":{"value":{"amount":"+0.9006120562553406","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":"Q2462663$45343132-38E3-43F7-AE0F-43E7BC795B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0fe9cf4a0b174cac59f0056e8d45b7523b1c7f8","datavalue":{"value":{"entity-type":"item","numeric-id":2330551,"id":"Q2330551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7577712434991976124b7059dc863eb50924be1c","datavalue":{"value":{"amount":"+0.862066388130188","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":"Q2462663$31E4C82E-C592-47DA-9875-DC7F590FD1A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32462fa0952cf99afe79dd155d29155533bdd48b","datavalue":{"value":{"entity-type":"item","numeric-id":2684236,"id":"Q2684236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4361b84a134e560d798a7a2b6942d48a27afb05","datavalue":{"value":{"amount":"+0.8535535931587219","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":"Q2462663$440F65B8-11D2-4306-93BE-5D7D96C78F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56955275274e425466f943de2ace948372cfcedb","datavalue":{"value":{"entity-type":"item","numeric-id":2118738,"id":"Q2118738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"571ca5c4ab2136af4a52234c2eca5d92272a3115","datavalue":{"value":{"amount":"+0.8534272909164429","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":"Q2462663$5E7365E3-0CE8-45D3-A303-2F22349D533E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de3ded53d0a225585690b132dbdfe961dc0d098a","datavalue":{"value":{"entity-type":"item","numeric-id":2240988,"id":"Q2240988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bdeb6be9f8c493cc41e1984c826fe4d22d44b0c","datavalue":{"value":{"amount":"+0.847762405872345","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":"Q2462663$95EAAE27-18A3-4ADA-BFBF-CD6E563B9343","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2462663","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2462663"}}}}}