NDLI: On the Power of Non-adaptive Learning Graphs

Content Provider	Springer Nature Link
Author	Rosmanis, Ansis Belovs, Aleksandrs
Copyright Year	2014
Abstract	We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein.Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it.For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and Špalek (Proceeding of 4th ACM ITCS, 323–328, 2013).Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem.
Ending Page	354
Page Count	32
Starting Page	323
File Format	PDF
ISSN	10163328
e-ISSN	14208954
Journal	Computational complexity
Issue Number	2
Volume Number	23
Language	English
Publisher	Springer Basel
Publisher Date	2014-05-13
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Quantum computing Quantum computation Computational Mathematics and Numerical Analysis triangle problem k-sum problem Quantum algorithms and complexity query algorithms adversary method Algorithm Analysis and Problem Complexity semidefinite optimization
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

A strong direct product theorem for quantum query complexity

THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

Parallel Approximation of Min-Max Problems

Quantum Separation of Local Search and Fixed Point Computation

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

Comparing the strength of query types in property testing: The case of k-colorability

Convex optimization for the planted k-disjoint-clique problem

On the Power of Non-adaptive Learning Graphs

Similar Documents

Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound

A strong direct product theorem for quantum query complexity

THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

Parallel Approximation of Min-Max Problems

Quantum Separation of Local Search and Fixed Point Computation

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

Comparing the strength of query types in property testing: The case of k-colorability

Convex optimization for the planted k-disjoint-clique problem

On the Power of Non-adaptive Learning Graphs