For the latest COVID-19 news and information, visit Penn State's Coronavirus Information website.

Export to Refworks Export to EndNote Email
Report an Issue

Quantum Decision Trees and Semidefinite Programming [electronic resource].

Published:
Washington, D.C. : United States. Dept. of Energy, 2001.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description:
12 pages : digital, PDF file
Additional Creators:
Los Alamos National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It

Finding items...

Restrictions on Access:
Free-to-read Unrestricted online access
Summary:
We reformulate the notion of quantum query complexity in terms of inequalities and equations for a set of positive matrices, which we view as a quantum analogue of a decision tree. Using the new formulation we show that: 1. every quantum query algorithm needs to use at most n quantum bits in addition to the query register. 2. For any function f there is an algorithm that runs in polynomial time in terms the truth table of f and (for {var_epsilon} > 0) computes the {var_epsilon}-error quantum decision tree complexity of f. 3. Using the dual of our system we can treat lower bound methods on a uniform platform, which paves the way to their future comparison. In particular we describe Ambainis's bound in our framework. 4. The output condition on quantum algorithms used by Ambainis and others is not sufficient for an algorithm to compute a function with {var_epsilon}-bounded error: we show the existence of algorithms whose final entanglement matrix satisfies the condition, but for which the value of f cannot be determined from a quantum measurement on the accessible part of the computer.
Report Numbers:
E 1.99:la-ur-01-6417
la-ur-01-6417
Subject(s):
Other Subject(s):
Note:
Published through SciTech Connect.
01/01/2001.
"la-ur-01-6417"
Submitted To the 34th Symposium on the Theory of Computing (STOC2002) Montreal, Canada, May 19-21, 2002.
Barnum, Howard; Saks, M.; Szegedy, M.
View MARC record | catkey: 14654645