(1) the name, physical address, e-mail address, and phone number of
EACH author,
Lee Spector
Cognitive Science, Hampshire College, Amherst, MA 01002
lspector@hampshire.edu, 413-559-5352
(2) the title of at least one paper published in the open literature
describing the work,
Book:
Automatic Quantum Computer Programming: A Genetic Programming Approach
Lee Spector. 2004. Boston: Kluwer Academic Publishers. ISBN
1-4020-7894-3.
(3) the abstract of the paper(s),
Since it's a book, it does not have an abstract per se. I am including
instead the introductory text from Chapter 8, Evolved Quantum Programs,
in which the new human-competitive results are described:
----
This chapter presents examples of the automatic production of quan-
tum computer programs via genetic programming. These examples
demonstrate how the techniques described in previous chapters can be
applied to specific problems. They also provide evidence for the claim
that scientifically significant results can be produced via automatic
quan-
tum computer programming.
The examples that are presented here are solutions to two types of
problems. We call problems of the first type "Boolean oracle analysis"
problems because they require us to determine some property of a pro-
vided Boolean quantum gate. This gate is often called an "oracle" or
a "black box" because we are given little a priori information about
the gate’s construction or behavior. All of these oracles are "Boolean"
in the sense that they act by inverting a particular single output qubit
when provided with specified combinations of inputs. We are allowed to
use the oracle gate, but we are not told in advance which combinations
of inputs will produce the inversion -- that is what a solution to the
problem will tell us. Sometimes we may be "promised" that the oracle
is one of some subset of the possible Boolean oracles of the given size;
in these cases the problem is to determine which member of the subset
we have been given.
An example of a Boolean oracle analysis problem is Grover’s database
search problem, which was discussed earlier in Chapter 2. In Grover’s
problem the oracle represents a database containing a single "marked"
item. We are promised that the oracle inverts its output for a single
com-
bination of inputs, which may be considered the address of the marked
item. Our task is to determine which of the possible inputs it is for
which the inversion is performed.
Other examples presented below -- the Deutsch-Jozsa (XOR) prob-
lem, the Majority-ON problem, and the OR and AND/OR problems --
are similar except that the "promises" that we are given about the ora-
cles and the features of the oracles that we are asked to determine vary
from problem to problem. For the Majority-ON problem we attempt
not just to solve a single instance of the problem but rather to produce
a scaling program that can solve instances of this problem of any size.
Several of these Boolean oracle analysis problems have practical sig-
nificance because their solutions directly enable us to solve difficult
real-
world problems more rapidly than is possible on classical computers;
for example, Grover’s algorithm can be used to provide a quadratic
speedup for a host of problems that involve search through unstructured
databases.
The second type of problem considered here concerns the classical
communication capacity of certain specific quantum gates. The prob-
lems of this type that are presented derive from recent research on the
tradeoffs between classical communication and entanglement-generating
powers of certain unitary transformations (Spector and Bernstein, 2003;
Bennett et al., 2004). In these problems the task is to transfer
informa-
tion from one set of qubits to another, without any direct connection
between the two sets of qubits aside from a single instance of the gate
under investigation. These problems are important not because they
have any direct practical application -- the gates under consideration
do not generally correspond to any real-world communication channels
-- but rather because their solutions contribute to the development of
the fundamental theory of quantum communication and computation.
Sections 8.1 through 8.5 describe specific problems, specific genetic
programming techniques that have been used to solve them, and inter-
esting features of evolved solutions. Particular emphasis is given to
the
author’s techniques described in Chapters 6 and 7 as they have been
applied in specific cases. Section 8.6 discusses the general
significance of
the results presented in Sections 8.1 through 8.5, both with respect to
the theory of quantum computation and with respect to techniques for
automatic quantum computer programming.
(4) PDF file of the paper(s), and
I have attached a PDF file of Chapter 8, which presents the specific
human-competitive results and their significance.
(5) a statement specifically identifying one or more of the eight
criteria (below) and stating why the result satisfies that criteria.
See examples (below) illustrating the form of the statement.
As described in Section 6 of the attached chapter ("Significance of
These Results"), several of the results satisfy the following two
criteria:
(B) The result is equal to or better than a result that was accepted as
a new scientific result at the time when it was published in a
peer-reviewed scientific journal.
(D) The result is publishable in its own right as a new scientific
result independent of the fact that the result was mechanically
created.
The specific claims being made for individual results are listed below.
First, however, a few words of clarification are in order regarding the
relation of the book's new results to results previously published by
myself and my colleagues, and regarding the sense in which criterion D
is being claimed to apply here. Each of the results claimed herein to
be human-competitive is a new, never before published quantum program
(first published in the 2004 book). However, for each of these results
(except for one -- the solution to the 1-bit Deutsch-Jozsa (XOR)
problem) a different but functionally equivalent evolved quantum
program also appeared in a paper, coauthored by me and my
collaborators, that was published previously. This has no bearing on
criterion B claims, but it muddies the water concerning criterion D
claims because the new results WOULD be publishable in their own right
(independent of the fact that they were mechanically created) EXCEPT
for the fact that different but functionally equivalent evolved quantum
programs appeared previously in my own coauthored publications. In the
claims below I use "D*" to mean "Would satisfy criterion D if not for
my own prior publication (with coauthors) of different but functionally
equivalent evolved quantum programs, which themselves did clearly
satisfy criterion D." Note also that in the book, where these criteria
are discussed, the word "result" is interpreted functionally -- that
is, a "result" in the book's discussion is an achieved input/output
relationship with an associated error probability. Here, by contrast, I
use "result" to mean a particular evolved quantum program.
RESULT: A solution to the 1-bit Deutsch-Jozsa (XOR) problem
BRIEF DESCRIPTION: Determine whether the behavior of a black-box quantum
oracle satisfies the XOR property using only one call to the oracle.
MEANS OF PRODUCTION: Genetic programming with PushGP
HUMAN-COMPETITIVE CRITERIA: B
EVIDENCE: Original results (by Deutch, Jozsa, and others) were published
as new and significant results.
RESULT: A solution to Grover's database search problem
BRIEF DESCRIPTION: Determine the location of a single marked item
in a 4-element quantum database using only one call to the database
access function.
MEANS OF PRODUCTION: Genetic programming with PushGP
HUMAN-COMPETITIVE CRITERIA: B
EVIDENCE: Original results (by Grover) were published as new and
significant results.
RESULT: A solution to the 1-bit OR problem
BRIEF DESCRIPTION: Determine whether the behavior of a black-box quantum
oracle satisfies the OR property using only one call to the oracle,
with
a probability of error no worse than 0.1.
MEANS OF PRODUCTION: Genetic programming with PushGP
HUMAN COMPETITIVE CRITERIA: B, D*
EVIDENCE: The first quantum program solving this problem, which was
produced
by genetic programming, was published by Barnum, Bernstein and
Spector
in Journal of Physics A: Mathematical and General.
RESULT: A solution to the 2-bit AND/OR problem
BRIEF DESCRIPTION: Determine whether the behavior of a black-box quantum
oracle satisfies the AND/OR property using only one call to the
oracle, with
a probability of error no worse than 0.2874.
MEANS OF PRODUCTION: Genetic programming with PushGP
HUMAN COMPETITIVE CRITERIA: B, D*
EVIDENCE: The first quantum program solving this problem, which was
produced
by genetic programming, was published by Barnum, Bernstein and
Spector
in Journal of Physics A: Mathematical and General.
Note: The attached chapter contains additional human-competitive
results (in Section 5, "Gate Communication Problems"), but those were
previously published before July 1, 2003, and so are not eligible for
this contest.