Synchrotron-based high-pressure research in materials science Page: 3 of 14
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to UNT Digital Library by the UNT Libraries Government Documents Department.
Extracted Text
The following text was automatically extracted from the image on this page using optical character recognition software:
in NP) with polynomially-checkable solutions. Q(f/n) is known to be a lower bound for OR [3] [4],
perhaps our best piece of evidence that NP BQP.
There are two major variants of the quantum query model: the exact model and the bounded
error model. In the exact model, we require that the quantum computation always output the
correct answer, and in the bounded error model we allow that on any input, the computation may
have a small probability e of being incorrect. We write QE (f) for the quantum complexity of f in
the exact model, and QE(f) for the quantum complexity of f in the bounded error model, where
e is the permissible error. (It is well known that for e E (0,1/2) the value of e only affects QE(f)
within a constant factor.) We also write D(f) for the determinstic decision tree complexity of f.
In the exact model, there are examples of surprising speedups, for example the 2 bit XOR can
be done exactly with one quantum query, but there are no known examples where exact quantum
computation provides more than a constant factor speedup over deterministic decision trees.
In the bounded error model, the OR function provides an example where quantum computation
gives a significant speedup over deterministic (and randomized) decision trees. In fact, the quadratic
speedup for OR is the best speedup result known for any boolean function. Perhaps the most
important problem in quantum query complexity is to resolve the following conjecture (which
seems to have been suggested by several researchers):
Conjecture 1 For any boolean function f and e E (0, 1/2), QE(f) = Q(D(f)1/2)
The best known result of this type says that for any f QE(f) = Q(D(f )1/6). It was obtained
by Beals, Buhrman, Cleve, Mosca, and de Wolf [6], via an extension to the quantum setting of
the polynomials methods introduced by Nisan and Szegedy [7]. It should be remarked that the
conjecture is for functions whose domain is all of {0, 1}n; for functions whose domain is restricted
(promise problems) there are much better speedups known, see e.g. [8]. In fact, the main component
of Shor's factoring algorithm [9] [10] is a query algorithm for the promise problem of finding the
period of a function by querying its table of values(cf. [11]).
The main result of this paper is to prove the conjecture for the class of read-once functions,
those functions expressible by a boolean formula in which each variable appears at most once.
Our results provide a quantum counterpart to the lower bounds on the randomized decision tree
complexity of read-once functions given in [12] and [13].
In [14], Ambainis introduced a lower bound technique for the quantum query model. He applied
this technique to obtain a Q(Vh) bound for a particular read-once function, the function which is
an OR of V/h disjoint ANDs of size Vfr, for which bounds were not previously known. The earlier
Bennett, Bernstein, Brassard, Vazirani lower bound [3] of V/7i on OR also turns out to be a case of
Ambainis' method.
Our method for obtaining the V/7i result generalizes Ambainis' method; in Section 3 we give
a generalization of his technique. Ambainis' approach is based on a thought-experiment in which
we imagine the computer to operate on a superposition of inputs in the query register. The idea
is that successful computation of a function requires, in the thought-experiment, "decoherence" of
initially coherently superposed inputs in the query register, having different values of the function.
This is because successful computation must correlate input states having different values of the
function with nearly orthogonal states in the part of the computer where the result is to be read. In
Ambainis' main results, the inputs are, essentially, taken to be superposed with equal coefficients.
The number of queries is bounded by comparing the required total amount of decoherence of a
judiciously selected set of input-output pairs to an upper bound on the amount achievable in a
single query step. Our result generalizes this technique to give a corresponding result using the
weighted total decoherence of input pairs (rather than just including/excluding pairs via weights2
Upcoming Pages
Here’s what’s next.
Search Inside
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Synchrotron-based high-pressure research in materials science, article, Date Unknown; [Los Alamos, New Mexico]. (https://digital.library.unt.edu/ark:/67531/metadc930969/m1/3/: accessed April 24, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT Libraries Government Documents Department.