RECORD
Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries
Quantum Physics · Submitted 15 Mar 2007
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We characterize the existence of an algorithm for such a query problem, with given error and number of queries, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of N by N ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given error and number of queries, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on black-box inputs having distinct function values, rather than bounded-error determinability of the function value via a single measurement on the output states, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of N by N ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. | background 0.60 | 0.54 | 0.05 | asserted 0.88 |
| s1 | We characterize the existence of an algorithm for such a query problem, with given error and number of queries, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. | result 0.59 | 0.94 | 0.62 | asserted 1.00 |
| s2 | Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on black-box inputs having distinct function values, rather than bounded-error determinability of the function value via a single measurement on the output states, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. | method 0.79 | 0.93 | 0.10 | asserted 1.00 |
| s3 | We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds. | contribution 0.56 | 0.94 | 0.28 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Generalizing earlier work characterizing the quantum query complexity of computing a function of an unknown classical ``black box'' function drawn from some set of such black box functions, we investigate a more general quantum query model in which the goal is to compute functions of N by N ``black box'' unitary matrices drawn from a set of such matrices, a problem with applications to determining properties of quantum physical systems. We characterize the existence of an algorithm for such a query problem, with given error and number of queries, as equivalent to the feasibility of a certain set of semidefinite programming constraints, or equivalently the infeasibility of a dual of these constraints, which we construct. Relaxing the primal constraints to correspond to mere pairwise near-orthogonality of the final states of a quantum computer, conditional on black-box inputs having distinct function values, rather than bounded-error determinability of the function value via a single measurement on the output states, we obtain a relaxed primal program the feasibility of whose dual still implies the nonexistence of a quantum algorithm. We use this to obtain a generalization, to our not-necessarily-commutative setting, of the ``spectral adversary method'' for quantum query lower bounds.
Human review
References
How the literature uses it
2 arXiv papers cite this in 5 sentences
Papers citing it · 3 sentences without a confident label
Uses its method or tool 1 paper
-
The goal here is to apply the semidefinite programming strategy originally developed for quantum query algorithms [ref] to the problem of optimizing clock interrogations.
Improving Quantum Clocks via Semidefinite Programming · Background and Summary · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.