Quantum query complexity and semi-definite programming

Howard Barnum, Michael Saks, Mario Szegedy

Research output: Contribution to journalConference articlepeer-review

81 Scopus citations


We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1. show that the workspace of a quantum computer can be limited to at most n + k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model. 2. give an algorithm that on input the truth table of a partial boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries. 3. use semidefinite programming duality to formulate a dual SDP P̂(f, t, ε) that is feasible if and only if f can not be evaluated within error ε by a t-step quantum query algorithm Using this SDP we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations. 4. Give an interpretation of a generalized form of branching in quantum computation.

Original languageEnglish (US)
Pages (from-to)179-193
Number of pages15
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - 2003
Event18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark
Duration: Jul 7 2003Jul 10 2003

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


Dive into the research topics of 'Quantum query complexity and semi-definite programming'. Together they form a unique fingerprint.

Cite this