License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06391.3
URN: urn:nbn:de:0030-drops-8769
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/876/
Go to the corresponding Portal

Barnum, Howard

Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries

pdf-format:
06391.BarnumHoward.Paper.876.pdf (0.2 MB)

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 imes 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 query and error, 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 the various black-box inputs, rather than bounded-error distinguishability,
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.

BibTeX - Entry

@InProceedings{barnum:DagSemProc.06391.3,
  author =	{Barnum, Howard},
  title =	{{Semidefinite programming characterization and spectral adversary method for quantum complexity with noncommuting unitary queries}},
  booktitle =	{Algorithms and Complexity for Continuous Problems},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6391},
  editor =	{Stephan Dahlke and Klaus Ritter and Ian H. Sloan and Joseph F. Traub},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/876},
  URN =		{urn:nbn:de:0030-drops-8769},
  doi =		{10.4230/DagSemProc.06391.3},
  annote =	{Keywords: Quantum query complexity semidefinite programming}
}

Keywords: Quantum query complexity semidefinite programming
Collection: 06391 - Algorithms and Complexity for Continuous Problems
Issue Date: 2007
Date of publication: 31.01.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI