Quantum tic-tac-toe

Last updated
An animation of the game being played QT3 animated opening.gif
An animation of the game being played

Quantum tic-tac-toe is a "quantum generalization" of tic-tac-toe in which the players' moves are "superpositions" of plays in the classical game. The game was invented by Allan Goff of Novatia Labs, who describes it as "a way of introducing quantum physics without mathematics", and offering "a conceptual foundation for understanding the meaning of quantum mechanics". [1] [2] [3] [4]

Contents

Background

The motivation to invent quantum tic-tac-toe was to explore what it means to be in two places at once. In classical physics, a single object cannot be in two places at once. In quantum physics, however, the mathematics used to describe quantum systems seems to imply that before being subjected to quantum measurement (or "observed") certain quantum particles can be in multiple places at once. (The textbook example of this is the double-slit experiment.) How the universe can be like this is rather counterintuitive. There is a disconnect between the mathematics and our mental images of reality, a disconnect that is absent in classical physics. This is why quantum mechanics supports multiple "interpretations".

The researchers who invented quantum tic-tac-toe were studying abstract quantum systems, formal systems whose axiomatic foundation included only a few of the axioms of quantum mechanics. Quantum tic-tac-toe became the most thoroughly studied abstract quantum system and offered insights that spawned new research. It also turned out to be a fun and engaging game, a game which also provides good pedagogy in the classroom.

The rules of quantum tic-tac-toe attempt to capture three phenomena of quantum systems:

superposition
the ability of quantum objects to be in two places at once.
entanglement
the phenomenon where distant parts of a quantum system display correlations that cannot be explained by either timelike causality or common cause.
collapse
the phenomenon where the quantum states of a system are reduced to classical states. Collapses occur when a measurement happens, but the mathematics of the current formulation of quantum mechanics is silent on the measurement process. Many of the interpretations of quantum mechanics derive from different efforts to deal with the measurement problem.

Gameplay

The second player has just made move O8. The first player must now choose whether to collapse O8 into the upper right square or the middle square. (Either way, O is going to get three-in-a-row.) QuantumTicTacToeUncollapsed.png
The second player has just made move O8. The first player must now choose whether to collapse O8 into the upper right square or the middle square. (Either way, O is going to get three-in-a-row.)
X has chosen to collapse O8 into the middle square, which forces the rest of the entanglements to collapse. This gives X their own three-in-a-row, but since the maximum subscript of O2O4O6 (namely, 6) is less than the maximum subscript of X1X3X7 (namely, 7), O gets one point while X gets only one-half point. O still wins. QuantumTicTacToeCollapsed.png
X has chosen to collapse O8 into the middle square, which forces the rest of the entanglements to collapse. This gives X their own three-in-a-row, but since the maximum subscript of O2O4O6 (namely, 6) is less than the maximum subscript of X1X3X7 (namely, 7), O gets one point while X gets only one-half point. O still wins.

Quantum tic-tac-toe captures the three quantum phenomena discussed above by modifying one basic rule of classical tic-tac-toe: the number of marks allowed in each square. Additional rules specify when and how a set of marks "collapses" into classical moves.

On each move, the current player marks two squares with their letter (X or O), instead of one, and each letter (X or O) is subscripted with the number of the move (beginning counting with 1). The pair of marks are called spooky marks. (Because X always moves first, [1] the subscripts on X are always odd and the subscripts on O are always even.)

For example, player 1's first move might be to place "X1" in both the upper left and lower right squares. The two squares thus marked are called entangled. During the game, there may be as many as eight spooky marks in a single square (if the square is entangled with all eight other squares).

The phenomenon of collapse is captured by specifying that a "cyclic entanglement" causes a "measurement". A cyclic entanglement is a cycle in the entanglement graph; for example, if

then these three squares form a cyclic entanglement. At the end of the turn on which the cyclic entanglement was created, the player whose turn it is not that is, the player who did not create the cycle chooses one of two ways to "measure" the cycle and thus cause all the entangled squares to "collapse" into classical tic-tac-toe moves. In the preceding example, since player 2 created the cycle, player 1 decides how to "measure" it. Player 1's two options are:

  1. X1 collapses into square 1. This forces O4 to collapse into square 8 and X3 to collapse into square 4.
  2. X1 collapses into square 4. This forces X3 to collapse into square 8 and O4 to collapse into square 1.

Any other chains of entanglements hanging off the cycle would also collapse at this time; for example, if square 1 were also entangled via O2 with square 5, then either measurement above would force O2 to collapse into square 5. (Note that it is impossible for two or more cyclic entanglements to be created in a single turn.)

When a move collapses into a single square, that square is permanently marked (in larger print) with the letter and subscript of the collapsed move a classical mark. A square containing a classical mark is fixed for the rest of the game; no more spooky marks may be placed in it.

The first player to achieve a tic-tac-toe (three in a row horizontally, vertically, or diagonally) consisting entirely of classical marks is declared the winner. Since it is possible for a single measurement to collapse the entire board and give classical tic-tac-toes to both players simultaneously, the rules declare that the player whose tic-tac-toe has the lower maximum subscript (representing the first completed line in the collapsed timeline) earns one point, and the player whose tic-tac-toe has the higher maximum subscript earns only one-half point.

See also

Related Research Articles

<span class="mw-page-title-main">Many-worlds interpretation</span> Interpretation of quantum mechanics

The many-worlds interpretation (MWI) is an interpretation of quantum mechanics that asserts that the universal wavefunction is objectively real, and that there is no wave function collapse. This implies that all possible outcomes of quantum measurements are physically realized in some "world" or universe. The evolution of reality as a whole in MWI is rigidly deterministic and local. Many-worlds is also called the relative state formulation or the Everett interpretation, after physicist Hugh Everett, who first proposed it in 1957. Bryce DeWitt popularized the formulation and named it many-worlds in the 1970s.

<span class="mw-page-title-main">Quantum mechanics</span> Description of physical properties at the atomic and subatomic scale

Quantum mechanics is a fundamental theory that describes the behavior of nature at and below the scale of atoms. It is the foundation of all quantum physics, which includes quantum chemistry, quantum field theory, quantum technology, and quantum information science.

<span class="mw-page-title-main">Quantum teleportation</span> Physical phenomenon

Quantum teleportation is a technique for transferring quantum information from a sender at one location to a receiver some distance away. While teleportation is commonly portrayed in science fiction as a means to transfer physical objects from one location to the next, quantum teleportation only transfers quantum information. The sender does not have to know the particular quantum state being transferred. Moreover, the location of the recipient can be unknown, but to complete the quantum teleportation, classical information needs to be sent from sender to receiver. Because classical information needs to be sent, quantum teleportation cannot occur faster than the speed of light.

<span class="mw-page-title-main">Qubit</span> Basic unit of quantum information

In quantum computing, a qubit or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics. Examples include the spin of the electron in which the two levels can be taken as spin up and spin down; or the polarization of a single photon in which the two spin states can also be measured as horizontal and vertical linear polarization. In a classical system, a bit would have to be in one state or the other. However, quantum mechanics allows the qubit to be in a coherent superposition of multiple states simultaneously, a property that is fundamental to quantum mechanics and quantum computing.

<span class="mw-page-title-main">Quantum entanglement</span> Correlation between quantum systems

Quantum entanglement is the phenomenon of a group of particles being generated, interacting, or sharing spatial proximity in such a way that the quantum state of each particle of the group cannot be described independently of the state of the others, including when the particles are separated by a large distance. The topic of quantum entanglement is at the heart of the disparity between classical and quantum physics: entanglement is a primary feature of quantum mechanics not present in classical mechanics.

<span class="mw-page-title-main">Schrödinger's cat</span> Thought experiment in quantum mechanics

In quantum mechanics, Schrödinger's cat is a thought experiment concerning quantum superposition. In the thought experiment, a hypothetical cat may be considered simultaneously both alive and dead, while it is unobserved in a closed box, as a result of its fate being linked to a random subatomic event that may or may not occur. This experiment viewed this way is described as a paradox. This thought experiment was devised by physicist Erwin Schrödinger in 1935 in a discussion with Albert Einstein to illustrate what Schrödinger saw as the problems of the Copenhagen interpretation of quantum mechanics.

<span class="mw-page-title-main">Tic-tac-toe</span> Paper-and-pencil game for two players

Tic-tac-toe, noughts and crosses, or Xs and Os is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with X or O. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner. It is a solved game, with a forced draw assuming best play from both players.

An interpretation of quantum mechanics is an attempt to explain how the mathematical theory of quantum mechanics might correspond to experienced reality. Quantum mechanics has held up to rigorous and extremely precise tests in an extraordinarily broad range of experiments. However, there exist a number of contending schools of thought over their interpretation. These views on interpretation differ on such fundamental questions as whether quantum mechanics is deterministic or stochastic, local or non-local, which elements of quantum mechanics can be considered real, and what the nature of measurement is, among other matters.

In quantum mechanics, wave function collapse, also called reduction of the state vector, occurs when a wave function—initially in a superposition of several eigenstates—reduces to a single eigenstate due to interaction with the external world. This interaction is called an observation, and is the essence of a measurement in quantum mechanics, which connects the wave function with classical observables such as position and momentum. Collapse is one of the two processes by which quantum systems evolve in time; the other is the continuous evolution governed by the Schrödinger equation.

<span class="mw-page-title-main">Quantum decoherence</span> Loss of quantum coherence

Quantum decoherence is the loss of quantum coherence. Quantum decoherence has been studied to understand how quantum systems convert to systems which can be explained by classical mechanics. Beginning out of attempts to extend the understanding of quantum mechanics, the theory has developed in several directions and experimental studies have confirmed some of the key issues. Quantum computing relies on quantum coherence and is one of the primary practical applications of the concept.

In quantum mechanics, the measurement problem is the problem of definite outcomes: quantum systems have superpositions but quantum measurements only give one definite result.

In quantum information science, the Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement. The Bell's states are a form of entangled and normalized basis vectors. This normalization implies that the overall probability of the particle being in one of the mentioned states is 1: . Entanglement is a basis-independent result of superposition. Due to this superposition, measurement of the qubit will "collapse" it into one of its basis states with a given probability. Because of the entanglement, measurement of one qubit will "collapse" the other qubit to a state whose measurement will yield one of two possible values, where the value depends on which Bell's state the two qubits are in initially. Bell's states can be generalized to certain quantum states of multi-qubit systems, such as the GHZ state for three or more subsystems.

In physics, the no-communication theorem or no-signaling principle is a no-go theorem from quantum information theory which states that, during measurement of an entangled quantum state, it is not possible for one observer, by making a measurement of a subsystem of the total state, to communicate information to another observer. The theorem is important because, in quantum mechanics, quantum entanglement is an effect by which certain widely separated events can be correlated in ways that, at first glance, suggest the possibility of communication faster-than-light. The no-communication theorem gives conditions under which such transfer of information between two observers is impossible. These results can be applied to understand the so-called paradoxes in quantum mechanics, such as the EPR paradox, or violations of local realism obtained in tests of Bell's theorem. In these experiments, the no-communication theorem shows that failure of local realism does not lead to what could be referred to as "spooky communication at a distance".

<span class="mw-page-title-main">Greenberger–Horne–Zeilinger state</span> "Highly entangled" quantum state of 3 or more qubits

In physics, in the area of quantum information theory, a Greenberger–Horne–Zeilinger state is a certain type of entangled quantum state that involves at least three subsystems. The four-particle version was first studied by Daniel Greenberger, Michael Horne and Anton Zeilinger in 1989, and the three-particle version was introduced by N. David Mermin in 1990. Extremely non-classical properties of the state have been observed, contradicting intuitive notions of locality and causality. GHZ states for large numbers of qubits are theorized to give enhanced performance for metrology compared to other qubit superposition states.

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:

  1. Superposed initial states,
  2. Quantum entanglement of initial states,
  3. Superposition of strategies to be used on the initial states.

Quantum pseudo-telepathy describes the use of quantum entanglement to eliminate the need for classical communications. A nonlocal game is said to display quantum pseudo-telepathy if players who can use entanglement can win it with certainty while players without it can not. The prefix pseudo refers to the fact that quantum pseudo-telepathy does not involve the exchange of information between any parties. Instead, quantum pseudo-telepathy removes the need for parties to exchange information in some circumstances.

In quantum physics, a quantum state is a mathematical entity that embodies the knowledge of a quantum system. Quantum mechanics specifies the construction, evolution, and measurement of a quantum state. The result is a prediction for the system represented by the state. Knowledge of the quantum state, and the rules for the system's evolution in time, exhausts all that can be known about a quantum system.

This is a glossary for the terminology applied in the foundations of quantum mechanics and quantum metaphysics, collectively called quantum philosophy, a subfield of philosophy of physics.

ER = EPR is a conjecture in physics stating that two entangled particles are connected by a wormhole and is thought by some to be a basis for unifying general relativity and quantum mechanics into a theory of everything.

<span class="mw-page-title-main">Tic-tac-toe variants</span>

Tic-tac-toe is an instance of an m,n,k-game, where two players alternate taking turns on an m×n board until one of them gets k in a row. Harary's generalized tic-tac-toe is an even broader generalization. The game can also be generalized as a nd game. The game can be generalised even further from the above variants by playing on an arbitrary hypergraph where rows are hyperedges and cells are vertices.

References

  1. 1 2 Goff, Allan; Lehmann, Dale; Siegel, Joel (2002-07-07). "Quantum Tic-Tac-Toe, Spooky-Coins & Magic-Envelopes, as Metaphors for Relativistic Quantum Physics" (PDF). 38th AIAA/ASME/SAE/ASEE Joint Propulsion Conference & Exhibit (PDF). doi:10.2514/6.2002-3763. ISBN   9781624101151. Archived from the original (PDF) on 2012-09-14.
  2. Goff, Allan (2004). "Quantum Tic-Tac-Toe as Metaphor for Quantum Physics". AIP Conference Proceedings. 699: 1152–1159. Bibcode:2004AIPC..699.1152G. doi:10.1063/1.1649685.
  3. Goff, Allan (2006). "Quantum tic-tac-toe: A teaching metaphor for superposition in quantum mechanics". American Journal of Physics. 74 (11): 962–973. Bibcode:2006AmJPh..74..962G. doi:10.1119/1.2213635. ISSN   0002-9505.
  4. Sagole, Sai; Dey, Anurit; Behera, Bikash; Panigrahi, Prasanta (2019-12-22). Quantum Tic-Tac-Toe: A Hybrid of Quantum and Classical Computing. doi:10.13140/rg.2.2.18883.76320.