(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.