Contemporary Mathematics

Quantum Games and Quantum Algorithms

David A. Meyer

Abstract. A quantum algorithm for an oracle problem can be understood as a quantum strategy for a player in a two-player zero-sum game in which the other player is constrained to play classically. I formalize this correspondence and give examples of games (and hence oracle problems) for which the quantum player can do better than would be possible classically. The most remarkable example is the Bernstein-Vazirani quantum search algorithm which I show creates no entanglement at any timestep.

1. Introduction

Despite the exuberance of people working on quantum computation—and more generally, quantum information theory—we discuss remarkably few quantum algorithms. These include, and are largely limited to, the Deutsch-Jozsa [1], Simon [2], Shor [3] and Grover [4] algorithms. Of course, quantum versions of many other information processing tasks have also been studied: cryptography [5], error correction [6], communication channels [7], distributed computation [8], etc. When I was invited to speak about quantum computing at Microsoft Research in January 1998, I decided to try to add game theory to this list.

My motivations were twofold: First, as I explained in that talk, von Neumann was not only the driving force behind the development of modern digital computers [9]—a subject of great interest to Microsoft—but also one of the founders of quantum mechanics [10], and thus someone whose ideas are central to quantum computing. But he had another great interest—shared with Microsoft—economics! Von Neumann essentially invented game theory [11]; his book with Morgenstern, Theory of Games and Economic Behavior [12] raises (and in some cases, answers) many of the questions which preoccupy game theorists and economists today. Second, I hoped that something like the argument that identifies which two-person zero-sum games have optimal mixed, rather than pure, classical strategies might provide some insight into which problems are solvable more efficiently by quantum rather than classical algorithms. This hope was probably somewhat naïve, but it brings us to the first question I’ll address in this talk: What do quantum games have to do with quantum algorithms?

\begin{matrix}c \\ ◯ \end{matrix}2002 American Mathematical Society

2000 Mathematics Subject Classification. Primary 81P68, 68Q15; Secondary 91A05.

Key words and phrases. quantum strategy, quantum algorithm, query complexity, entanglement.

The quantum game I described originally [13], PQ PENNY FLIP, is perhaps too simple to make the connection with quantum algorithms completely clear. In fact, it is so simple, involving only one qubit, that several people have pointed out that it could be simulated classically [14]. I have argued elsewhere that this misses the point slightly, that the issue is not whether there exists a classical simulation, but how the complexity of that simulation would scale if the size of the game were to increase [15]. To illustrate this point explicitly, in this talk I’ll tell a story which involves a game which has instances of arbitrarily large size. My discussion of this game naturally includes a description of Grover’s algorithm [4], which not only helps to answer the first question, but raises a second and third.

The second is: Are there sophisticated quantum search algorithms? More explicitly, are there ‘databases’ which can be ‘searched’ with better than the square root speedup that Grover’s algorithm provides over the best possible classical algorithm? [4] Since Bennett, Bernstein, Brassard and Vazirani [16], Boyer, Brassard, Høyer and Tapp [17], and Zalka [18] have shown that Grover’s algorithm is optimal, I will explain the natural changes in the problem which make this question interesting.

Recently Lloyd has argued that Grover’s algorithm can be implemented without entanglement [19]. At first glance this may appear surprising: many people have stated that the power of quantum computing derives from entanglement [20,21]. This belief underlies the criticism that NMR experiments do not realize quantum computation because the state of the system at each timestep is separable [22], i.e., a convex combination of product states [23]. Similarly, van Enk observed that the one qubit PQ PENNY FLIP game not only can be simulated classically, but involves no entanglement [14], which would suggest by the same ‘reasoning’ that such a quantum game would be unrelated to quantum algorithms. In fact, the quantum game in the story to come provides an answer to the third question I’ll address: Can quantum-over-classical improvements be achieved without entanglement?

2. PQ games

I’ll begin by reviewing briefly the one qubit game PQ PENNY FLIP [13]. In our first episode, the starship Enterprise is facing some imminent catastrophe when the superpowerful being Q appears on the bridge and offers to rescue the ship if Captain Picard^{1} can beat him at a simple game: Q produces a penny and asks Picard to place it in a small box, head up. Then Q, followed by Picard, followed by Q, reaches into the box, without looking at the penny, and either flips it over or leaves it as it is. After Q’s second turn they open the box and Q wins if the penny is head up. Q wins every time they play, using the following quantum strategy:

|0⟩ ⟼_{H}^{Q} \frac{1}{\sqrt{2}}(|0⟩ + |1⟩)

⟼_{σ_{x} or I_{2}}^{Picard} \frac{1}{\sqrt{2}}(|0⟩ + |1⟩)

⟼_{H}^{Q} |0⟩

1Captain Picard and Q are characters in the popular American television (and movie) series Star Trek: The Next Generation whose initials and abilities are ideal for this illustration. See [24].

Here |·⟩ is Dirac notation [25] for an element of Hilbert space, 0 denotes ‘head’ and 1 denotes ‘tail’, H = \frac{1}{\sqrt{2}}({1 \atop 1} {1 \atop −1}) is the Hadamard transformation, and σ_{x} = ({0 \atop 1} {1 \atop 0}) implements Picard’s possible action of flipping the penny over. Q’s quantum strategy of putting the penny into the equal superposition of ‘head’ and ‘tail’ on his first turn means that whether Picard flips the penny over or not, it remains in an equal superposition which Q can rotate back to ‘head’ by applying H again since H = H^{−1}. So when they open the box, Q always wins.

Notice that if Q were restricted to playing classically, i.e., to implementing only σ_{x} or I_{2} on his turns, an optimal strategy for both players would be to flip the penny over or not with equal probability on each turn. In this case Q would win only half the time, so he does substantially better by playing quantum mechanically.

The structure of PQ PENNY FLIP motivates the following definition which formalizes one meaning for quantum game.^{2} Definitions. A PQ game consists of

(i) a Hilbert space H—the possible states of the game—with N = dimH, (ii) an initial state ψ_{0} ∈ H, (iii) subsets Q_{i} ⊂ U(N), i ∈ {1, …, k + 1}—the elements of Q_{i} are the moves

Q chooses among on turn i, (iv) subsets P_{i} ⊂ S_{N}, i ∈ {1, …, k}, where S_{N} is the permutation group on N elements—the elements of P_{i} are the moves Picard chooses among on turn i, and

(v) a projection operator Π on H—the subspace W_{Q} fixed by Π consists of the winning states for Q.

Since only Picard and Q play, these are two-player games; they are zero-sum since when Q wins, Picard loses, and vice versa.

A pure quantum strategy for Q is a sequence (u_{i} ∈ Q_{i})_{i=1}^{k+1}. A pure (classical) strategy for Picard is a sequence (s_{i} ∈ P_{i})_{i=1}^{k}, while a mixed (classical) strategy for Picard is a sequence of probability distributions (f_{i} : P_{i} → [0, 1])_{i=1}^{k}. If both Q and Picard play pure strategies, the corresponding evolution of the PQ game is described by

ψ_{f} = u_{k+1}s_{k}u_{k} … u_{2}s_{1}u_{1}ψ_{0}.

After Q’s last move the state of the game is measured with Π. According to the rules of quantum mechanics [10], the players observe the eigenvalue 1 with probability Tr(ψ^{†}Πψ); this is the probability that the state is projected into W_{Q} and Q wins. More generally, if Picard plays a mixed strategy, the corresponding evolution of the PQ game is described by

ρ_{f} = u_{k+1}( ∑_{s_{k}∈P_{k}} f_{k}(s_{k})s_{k}u_{k} … u_{2}( ∑_{s_{1}∈P_{1}} f_{1}(s_{1})s_{1}u_{1}ρ_{0}u_{1}^{†}s_{1}^{†})u_{2}^{†} … u_{k}^{†}s_{k}^{†})u_{k+1}^{†},

where ρ_{0} = ψ_{0} ⊗ ψ_{0}^{†}. Again, after Q’s last move ρ_{f} is measured with Π; the probability that ρ_{f} is projected into W_{Q} ⊗ W_{Q}^{†} and Q wins is Tr(Πρ_{f}).

2Eisert, Wilkens and Lewenstein have proposed a different formalism for quantum games and have applied it to find a (unique) Pareto optimal equilibrium for the Prisoners’ Dilemma when the players are allowed to select moves from the same specific subset of unitary transformations [26].

Benjamin and Hayden recently showed that this is not a solution when the players are allowed to make arbitrary unitary moves [27]; in fact, in this case there is no equilibrium, just as in PQ PENNY FLIP [13]. Nevertheless, that formalism still seems likely to be interesting, although more closely related to quantum communication protocols [8,28] than to quantum algorithms.

Finally, an equilibrium is a pair of strategies, one for Picard and one for Q, such that neither player can improve his probability of winning by changing his strategy while the other does not.

As I’ll show in the next section, the structure of a PQ game specializes to the structure of the known quantum algorithms. In general, unlike the simple case of PQ PENNY FLIP, W_{Q} = W_{Q}((s_{i})) or W_{Q} = W_{Q}((f_{i})), i.e., the conditions for Q’s win can depend on Picard’s strategy. Each of the three example games I consider here suffices to prove that there are games with mixed/quantum equilibria at which Q does better than he would at any mixed/mixed equilibrium; equivalently, there are some quantum algorithms which outperform classical ones.

3. Guessing a number

In our second episode, Q returns to the Enterprise and challenges Captain Picard again. He boasts that if Picard picks any number between 0 and N − 1, inclusive, he can guess it. Now, Picard is no slouch; he has been studying up on quantum algorithms since the last episode. In particular, he has studied Grover’s algorithm [4] and realizes that for N = 2^{n}, Q can determine the number he picks with high probability by playing the following strategy:

|0 … 0, 0⟩  ⟼_{H^{⊗n}⊗Hσ_{x}}^{Q}  \frac{1}{\sqrt{N}} ∑_{x=0}^{N−1} |x⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩)  (u_{1})

⟼_{s(f_{a})}^{Picard}  \frac{1}{\sqrt{N}} ∑_{x=0}^{N−1}(−1)^{δ_{xa}}|x⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩) (s_{1})
⟼_{H^{⊗n}⊗I_{2}∘s(f_{0})∘H^{⊗n}⊗I_{2}}^{Q} ⋯,  (u_{2})

where a ∈ [0, N − 1] is Picard’s chosen number, and the moves s_{1} and u_{2} are repeated a total of k = ⌊\frac{π}{4} \sqrt{N}⌋ times, i.e., s_{k} = ⋯ = s_{1} and u_{k+1} = ⋯ = u_{2}. For f : ℤ_{2}^{n} → ℤ_{2}, s(f) is the permutation (and hence unitary transformation) defined by

s(f)|x, b⟩ = |x, b ⊕ f(x)⟩,

where ⊕ denotes addition mod 2. This transformation is often referred to as ‘fcontrolled-NOT’. Each of Picard’s moves s_{i} can be thought of as the response of an oracle which computes f_{a}(x) := δ_{xa} to respond to the quantum query defined by the state after u_{i}. After O(\sqrt{N}) such queries, a measurement by Π = |a⟩⟨a|⊗I_{2} returns a win for Q with probability bounded above \frac{1}{2}, i.e., Grover’s quantum algorithm determines a with high probability. (Here ⟨a| := |a⟩^{†} and the tensor product is implicit in |a⟩⟨a| [25].)

Notice that if Q were to play classically, he could query Picard about a specific number at each turn, but on the average it would take N/2 turns to guess a. A classical equilibrium is for Picard to choose a uniformly at random, and for Q to choose a permutation of N uniformly at random and guess numbers in the corresponding order. Even when Picard plays such a mixed strategy, Q’s quantum strategy is optimal; together they define a mixed/quantum equilibrium.

Knowing all this, Picard responds that he will be happy to play, but that Q should only get 1 guess, not ⌊\frac{π}{4} \sqrt{N}⌋. Q protests that this is hardly fair, but he will play, as long as Picard tells him how close (mod 2) his guess is to the chosen number. Picard agrees, and they play. Q wins. They play again. Q wins again. Picard doesn’t understand what’s going on. The problem is that in his studies of quantum algorithms, he overlooked an insufficiently appreciated quantum algorithm, the slightly improved [16,29] Bernstein-Vazirani algorithm [30]: Guess x and answer a are vectors in ℤ_{2}^{n}, so x · a depends on the cosine of the angle between the vectors. Thus it seems reasonable to define “how close (mod 2) a guess is to the answer” to be the oracle response g_{a}(x) := x · a mod 2. Then Q plays as follows:

|0 … 0, 0⟩ ⟼_{H^{⊗n}⊗Hσ_{x}}^{Q} \frac{1}{\sqrt{N}} ∑_{x=0}^{N−1} |x⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩)  (u_{1})

⟼_{s(g_{a})}^{Picard} \frac{1}{\sqrt{N}} ∑_{x=0}^{N−1}(−1)^{x·a}|x⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩) (s_{1})
⟼_{H^{⊗n}⊗I_{2}}^{Q} |a⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩)  (u_{2})

For Π = |a⟩⟨a| ⊗ I_{2} again, Q wins with probability 1, having queried Picard only once!

Just as before, Picard makes the game hardest for Q classically if he chooses a uniformly at random. Classically Q requires n queries to determine a with probability 1. The classical to quantum improvement in number of queries is thus n to 1, in some sense greater than the Grover improvement from O(N) to O(\sqrt{N}).

4. Entanglement

Most remarkably, Bernstein and Vazirani’s ‘sophisticated’ quantum search algorithm achieves this improvement without creating any entanglement at any timestep! Recall the following definition: Definition. A pure state—a vector in H—is entangled if it does not factor relative to a given tensor product decomposition of the Hilbert space [31].

In the two algorithms considered in the previous sections, the Hilbert space decomposes into a tensor product of qubits [32], i.e., ℂ^{2}s. To see that the slightly improved [16,29] Bernstein-Vazirani algorithm [30] creates no entanglement relative to this decomposition, note that ψ_{0} has no entanglement, and hence u_{1}ψ_{0} has none since u_{1} is the tensor product of operations on individual qubits. Also, ψ_{f} is not entangled since |a⟩ is just the tensor product of qubits in states |0⟩ or |1⟩. But ψ_{f} is obtained from the intermediate state s_{1}u_{1}ψ_{0} by the action of u_{2} which, like u_{1}, is the tensor product of operations on individual qubits. So s_{1}u_{1}ψ_{0} also is not entangled.

In contrast, for Grover’s algorithm, every state after u_{1}ψ_{0} is entangled for n > 2. By a natural measure, the entanglement oscillates with period \frac{π}{4} \sqrt{N}, i.e., after ⌊\frac{π}{4} \sqrt{N}⌋ queries the state is close to |a⟩ ⊗ \frac{1}{\sqrt{2}}(|0⟩ − |1⟩) and its entanglement is

fairly small, while after only ⌊\frac{π}{8} \sqrt{N}⌋ queries the entanglement is fairly large [33]. So what could be the suggestion of Lloyd, to which I alluded in the Introduction, that Grover’s algorithm can be implemented without entanglement [19]? He simply observes that since the first n qubits are never entangled with the last qubit, if they are implemented by a single tensor factor of dimension N, there is no entanglement. This is true, of course, by definition, and has been observed earlier in the general quantum computing setting by Jozsa and Ekert [20]. The cost incurred for realizing such a scheme physically, as Lloyd acknowledges, increases exponentially with n and must be paid with increasing energy, mass, or precision.

5. Conclusion

So what do quantum games have to do with quantum algorithms? The two versions of GUESS A NUMBER illustrate the relation for oracle problems. In these cases, quantum algorithms specialize the PQ game definition to require that s_{1} = ⋯ = s_{k}, i.e., the oracle always responds the same way once a function has been chosen. Furthermore, the winning states for Q, W_{Q}, depend on Picard’s strategy (s_{i})_{i=1}^{k}, i.e., on a. The Deutsch-Jozsa [1], Simon [2] and Shor [3] algorithms can also be described this way.

Are there ‘sophisticated’ quantum algorithms? Yes. The oracle which responds in the Bernstein-Vazirani scenario with x · a mod 2 is a ‘sophisticated database’ by comparison with Grover’s ‘naïve database’ which only responds that a guess is correct or incorrect. The former is closely related to the vector space model for information retrieval in which there is a vector space with basis vectors corresponding to the occurrence of key words: database elements define vectors in this space and are ranked according to their inner product with the vector representing a query [34]. Furthermore, in some sense it improves more over the classical optimum than does Grover’s algorithm.

And finally, is entanglement required for quantum-over-classical improvements? No. I’ve shown that, remarkably, the slightly improved version of the Bernstein-Vazirani algorithm does not create entanglement at any timestep, but still solves this oracle problem with fewer queries than is possible classically. Relative to the oracle, this quantum algorithm has no entanglement, unlike Grover’s, which does— at least within the standard model of quantum computing. It illustrates both ‘sophisticated quantum search’ without entanglement and sophisticated “quantum search without entanglement” [35].

6. Acknowledgements

I thank Mike Freedman, Manny Knill, Raymond Laflamme, John Smolin and Nolan Wallach for useful discussions. This work was partially supported by Microsoft Research and by the National Security Agency (NSA) and Advanced Research and Development Activity (ARDA) under Army Research Office (ARO) contract number DAAG55-98-1-0376.

References

[1] D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation”, Proc. Roy. Soc. Lond. A 439 (1992) 553–558.

[2] D. R. Simon, “On the power of quantum computation”, in S. Goldwasser, ed., Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20–22 November 1994 (Los Alamitos, CA: IEEE Computer Society Press 1994) 116–123; D. R. Simon, “On the power of quantum computation”, SIAM J. Comput. 26 (1997) 1474–1483.

[3] P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring”, in S. Goldwasser, ed., Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20–22 November 1994 (Los Alamitos, CA: IEEE Computer Society Press 1994) 124–134; P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput. 26 (1997) 1484–1509.

[4] L. K. Grover, “A fast quantum mechanical algorithm for database search”, in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, PA, 22–24 May 1996 (New York: ACM 1996) 212–219.

[5] S. Wiesner, “Conjugate coding”, SIGACT News 15 (1983) 78–88; C. H. Bennett and G. Brassard, “Quantum cryptography: Public-key distribution and coin tossing”, in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, December 1984 (New York: IEEE 1984) 175–179; A. Ekert, “Quantum cryptography based on Bell’s theorem”, Phys. Rev. Lett. 67 (1991) 661–663.

[6] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory”, Phys. Rev. A 52 (1995) R2493–R2496; A. M. Steane, “Error correcting codes in quantum theory”, Phys. Rev. Lett. 77 (1996) 793–797.

[7] A. S. Kholevo, “Bounds for the quantity of information transmitted by a quantum communication channel”, Problemy Peredachi Informatsii 9 (1973) 3–11; transl. in Problems Inf. Transmiss. 9 (1973) 177–183; C. H. Bennett, D. P. DiVincenzo, J. Smolin and W. K. Wootters, “Mixed state entanglement and quantum error correction”, Phys. Rev. A 54 (1996) 3824– 3851; B. Schumacher, M. Westmoreland and W. K. Wootters, “Limitation on the amount of accessible information in a quantum channel”, Phys. Rev. Lett. 76 (1997) 3452–3455.

[8] R. Cleve and H. Buhrman, “Substituting quantum entanglement for communication”, Phys. Rev. A 56 (1997) 1201–1204; H. Buhrman, W. van Dam, P. Høyer and A. Tapp, “Multiparty quantum communication complexity”, Phys. Rev. A 60 (1999) 2737–2741.

[9] J. von Neumann, in A. H. Taub, ed., Collected Works, Vol. 5, Design of Computers, Theory of Automata and Numerical Analysis (New York: Pergamon Press 1961–1963).

[10] J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Berlin: Springer-Verlag 1932); transl. by R. T. Beyer as Mathematical Foundations of Quantum Mechanics (Princeton: Princeton University Press 1955).

[11] J. von Neumann, “Zur theorie der gesellschaftsspiele”, Math. Ann. 100 (1928) 295–320.

[12] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, third edition (Princeton: Princeton University Press 1953).

[13] D. A. Meyer, “Quantum strategies”, Phys. Rev. Lett. 82 (1999) 1052–1055.

[14] See, e.g., S. J. van Enk, “Quantum and classical game strategies”, Phys. Rev. Lett. 84 (2000) 789.

[15] D. A. Meyer, “Why quantum strategies are quantum mechanical”, published as “Meyer replies”, Phys. Rev. Lett. 84 (2000) 790.

[16] C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani, “Strengths and weaknesses of quantum computing”, SIAM J. Comput. 26 (1997) 1510–1523.

[17] M. Boyer, G. Brassard, P. Høyer and A. Tapp, “Tight bounds on quantum searching”, Fortsch. Phys. 46 (1998) 493–506.

[18] C. Zalka, “Grover’s quantum searching algorithm is optimal”, Phys. Rev. A 60 (1999) 2746– 2751.

[19] S. Lloyd, “Quantum search without entanglement”, Phys. Rev. A 61 (1999) 010301.

[20] R. Jozsa, “Entanglement and quantum computation”, in S. A. Huggett, L. J. Mason, K. P. Tod, S. T. Tsou and N. M. J. Woodhouse, eds., The Geometric Universe: Science, Geometry, and the Work of Roger Penrose (Oxford: Oxford University Press 1998) 369–379; A. Ekert and R. Jozsa, “Quantum algorithms: entanglement-enhanced information processing”, Phil. Trans. Roy. Soc. Lond. A 356 (1998) 1769–1782.

[21] A. M. Steane, “A quantum computer needs only one universe”, quant-ph/0003084.

[22] S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popescu and R. Schack, “Separability of very noisy mixed states and implications for NMR quantum computing”, Phys. Rev. Lett. 83 (1999) 1054–1057; R. Schack and C. M. Caves, “Classical model for bulk-ensemble NMR quantum computation”, Phys. Rev. A 60 (1999) 4354–4362. For a response to this criticism, see R. Laflamme, “Review of ‘Separability of very noisy mixed states and implications for NMR quantum computing’ ”, Quick Reviews in Quantum Computation and Information,

http://quickreviews.org/qc/.

[23] R. F. Werner, “Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model”, Phys. Rev. A 40 (1989) 4277–4281.

[24] L. M. Krauss, The Physics of Star Trek, with a foreword by Stephen Hawking (New York: HarperCollins 1995).

[25] P. A. M. Dirac, The Principles of Quantum Mechanics, fourth edition (Oxford: Oxford University Press 1958).

[26] J. Eisert, M. Wilkens and M. Lewenstein, “Quantum games and quantum strategies”, Phys. Rev. Lett. 83 (1999) 3077–3080.

[27] S. C. Benjamin and P. M. Hayden, “Comment on ‘Quantum games and quantum strategies’ ”, Phys. Rev. Lett. 87 (2001) 069801/1.

[28] A. M. Steane and W. van Dam, “Physicists triumph at guess my number”, Phys. Today 53(2) (February 2000) 35–39.

[29] R. Cleve, A. Ekert, C. Macchiavello and M. Mosca, “Quantum algorithms revisited”, Proc. Roy. Soc. Lond. A 454 (1998) 339–354.

[30] E. Bernstein and U. Vazirani, “Quantum complexity theory”, in Proceedings of the 25th ACM Symposium on Theory of Computing, San Diego, CA, 16–18 May 1993 (New York: ACM Press 1993) 11–20; E. Bernstein and U. Vazirani, “Quantum complexity theory”, SIAM J. Comput. 26 (1997) 1411–1473. A similar algorithm was rediscovered independently in B. M. Terhal and J. A. Smolin, “Single quantum querying of a database”, Phys. Rev. A 58 (1998) 1822–1826.

[31] E. Schrödinger, “Die gegenwärtige Situation in der Quantenmechanik”, Naturwissenschaften 23 (1935) 807–812; 823–828; 844–849.

[32] B. Schumacher, “Quantum coding (information theory)”, Phys. Rev. A 51 (1995) 2738–2747.

[33] D. A. Meyer and N. R. Wallach, “Global entanglement in multiparticle systems”,

quant-ph/0108104.

[34] G. Salton and M. McGill, Introduction to Modern Information Retrieval (New York: McGraw-Hill 1983); M. W. Berry, Z. Drmač and E. R. Jessup, “Matrices, vector spaces, and information retrieval”, SIAM Rev. 41 (1999) 335–362.

[35] D. A. Meyer, “Sophisticated quantum search without entanglement”, Phys. Rev. Lett. 85 (2000) 2014–2017.

(David A. Meyer) Project in Geometry and Physics, Department of Mathematics, University of California/San Diego, La Jolla, CA 92093-0112

E-mail address, David A. Meyer: dmeyer@chonji.ucsd.edu