Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries
| dc.creator | Barnum, Howard N. | |
| dc.date | 2007-03-15 | |
| dc.date.accessioned | 2026-07-07T07:52:11Z | |
| dc.date.available | 2026-07-07T07:52:11Z | |
| dc.description | 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. | |
| dc.description | Dagstuhl Seminar Proceedings 06391, "Algorithms and Complexity for Continuous Problems," ed. S. Dahlke, K. Ritter, I. H. Sloan, J. F. Traub (2006), available electronically at http://drops.dagstuhl.de/portals/index.php?semnr=06391 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0703141 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0703141 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125788 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries | |
| dc.type | text |