dorsal/arxiv
View SchemaSemidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries
| Authors | Howard N. Barnum |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0703141 |
| URL | https://arxiv.org/abs/quant-ph/0703141 |
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.
{
"annotation_id": "b2b41312-58cd-4da2-98fd-593e8d759b8a",
"date_created": "2026-03-02T18:02:34.374000Z",
"date_modified": "2026-03-02T18:02:34.374000Z",
"file_hash": "1684bb6975ccf315ba9fa37bf2f5e4649c6535e22c31f7721c105fe7007b909f",
"private": false,
"record": {
"abstract": "Generalizing earlier work characterizing the quantum query complexity of\ncomputing a function of an unknown classical ``black box\u0027\u0027 function drawn from\nsome set of such black box functions, we investigate a more general quantum\nquery model in which the goal is to compute functions of N by N ``black box\u0027\u0027\nunitary matrices drawn from a set of such matrices, a problem with applications\nto determining properties of quantum physical systems. We characterize the\nexistence of an algorithm for such a query problem, with given error and number\nof queries, as equivalent to the feasibility of a certain set of semidefinite\nprogramming constraints, or equivalently the infeasibility of a dual of these\nconstraints, which we construct. Relaxing the primal constraints to correspond\nto mere pairwise near-orthogonality of the final states of a quantum computer,\nconditional on black-box inputs having distinct function values, rather than\nbounded-error determinability of the function value via a single measurement on\nthe output states, we obtain a relaxed primal program the feasibility of whose\ndual still implies the nonexistence of a quantum algorithm. We use this to\nobtain a generalization, to our not-necessarily-commutative setting, of the\n``spectral adversary method\u0027\u0027 for quantum query lower bounds.",
"arxiv_id": "quant-ph/0703141",
"authors": [
"Howard N. Barnum"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries",
"url": "https://arxiv.org/abs/quant-ph/0703141"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1e42e1e0-6437-45b6-a536-f6b49dc4e7de",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}