The concept of a model of quantum computation is, for the discerning mind, a rather essential framework. Within this framework, the Turing machine , a theoretical bedrock of classical computation, finds its quantum counterpart. It’s a lineage that begins with the simple yet profound idea of a universal computational device, extending into realms where the rules of reality itself bend to new paradigms.

For those attempting to navigate this labyrinth of theoretical machines, it’s worth noting the various iterations of the Turing machine itself:

Machine Variants, a Taxonomy of Computational Endeavors:

• Turing machine equivalents : These are the conceptual siblings, all possessing the same computational power as the original, proving that even in abstraction, there are many paths to the same destination.
• Turing machine examples : Concrete illustrations for those who prefer their abstractions with a side of tangible demonstration.

Specialized Iterations, for When the Standard Model Isn’t Quite Enough:

• Alternating Turing machine : Introducing the delightful complexity of existential and universal quantification to computation.
• Neural Turing machine : Where the classical machine attempts to don the garb of neural networks, a testament to humanity’s persistent efforts to mimic itself.
• Nondeterministic Turing machine : A machine that, rather conveniently, can explore multiple computational paths simultaneously, a concept that hints at the very nature of its quantum successor.
• Quantum Turing machine: The subject at hand, a device that truly embraces the parallel realities of quantum mechanics.
• Post–Turing machine : A variation, often overlooked, yet significant in its own right, illustrating the diverse theoretical landscape.
• Probabilistic Turing machine : For when certainty is an overrated commodity, and outcomes are governed by chance, a step closer to the inherent unpredictability of the quantum realm.
• Multitape Turing machine : Because one tape is simply not enough for some computational ambitions, increasing capacity for more complex operations.
• Multi-track Turing machine : An optimization, allowing multiple channels of information on a single tape, a practical enhancement.
• Symmetric Turing machine : Exploring specific computational symmetries, a niche but important theoretical construct.
• Total Turing machine : Also known as a decider, this machine is guaranteed to halt, always providing an answer, unlike its more open-ended cousins.
• Unambiguous Turing machine : A deterministic cousin to the nondeterministic one, ensuring that if a solution exists, it is unique.
• Universal Turing machine : The quintessential machine, capable of simulating any other Turing machine , a foundational concept that underpins all modern computation.
• Zeno machine : A purely theoretical construct that performs an infinite number of steps in a finite amount of time, a delightful thought experiment that mostly serves to highlight the limits of physical reality.

The Minds Behind the Machines:

• Alan Turing : The progenitor, whose insights laid the groundwork for everything that followed, a mind that understood the essence of computation before it was even built.
• Category:Turing machine : A rather uninspired classification, but useful for those seeking a comprehensive, if dry, listing.

The Quantum Turing Machine: An Abstraction of the Unimaginable

A quantum Turing machine (QTM), often referred to as a universal quantum computer in its idealized form, is an abstract machine meticulously designed to model the profound and often counter-intuitive effects inherent in a quantum computer . It stands as a testament to the human intellect’s capacity to formalize even the most esoteric phenomena. This model, despite its theoretical simplicity, captures the entirety of quantum computation’s power. Consequently, any conceivable quantum algorithm can be rigorously expressed and analyzed within the framework of a particular quantum Turing machine .

However, in practice, the computationally equivalent quantum circuit model has gained more widespread adoption and recognition within the field. While the QTM provides a foundational theoretical understanding, the circuit model offers a more direct and often more intuitive representation for constructing and visualizing quantum operations, particularly for experimentalists and practical algorithm designers. 1 2 :2

The intricate relationship between quantum Turing machines and their classical or probabilistic Turing machine predecessors can be elegantly articulated through a mathematical construct based on transition matrices . This framework allows for a formal comparison and understanding of their respective computational capabilities. Specifically, one can define a matrix whose product with a matrix representing a classical or probabilistic machine yields the quantum probability matrix that characterizes the quantum machine. This significant insight was notably demonstrated by Lance Fortnow 3 , providing a bridge between the disparate computational paradigms.

Informal Sketch: Painting with Quantum States

For those who prefer a conceptual overview before diving into the mathematical abyss, a pragmatic way of approaching the quantum Turing machine (QTM) is to view it as a direct, albeit profound, generalization of the classical Turing machine (TM). This generalization mirrors the relationship between the quantum finite automaton (QFA) and its classical, deterministic finite automaton (DFA) counterpart. The core transformation lies in the nature of the machine’s internal states and its operational dynamics.

Instead of the discrete, classical internal states of a traditional Turing machine , the QTM operates with states that exist within a Hilbert space . These can be either pure or mixed states , reflecting the probabilistic and superpositional nature of quantum mechanics. Furthermore, the deterministic transition function of a classical machine, which dictates a single, unambiguous next step, is replaced by a collection of unitary matrices . These matrices perform automorphisms on the Hilbert space , ensuring that the evolution of the quantum state is always reversible and preserves its probabilistic interpretation 4 .

The Unsolved Problem: Simulating Reality

Before we delve deeper into the formal adaptations, let’s briefly acknowledge a rather pressing, if inconvenient, conundrum that haunts the fringes of this field:

Unsolved problem in physics Is a universal quantum computer sufficient to efficiently simulate an arbitrary physical system? More unsolved problems in physics

This question, a tantalizing blend of theoretical computer science and fundamental physics, underscores the profound implications of quantum computation. If the answer is yes, then the universe itself might just be a very large, very complex quantum computer, and we’re merely processing its output. If no, then we’re still missing a piece of the cosmic puzzle.

Formal Adaptations: Reimagining the 7-Tuple

A classical Turing machine is formally defined by a 7-tuple :

$M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$

For a more comprehensive understanding of each component, one might consult the formal definition of a Turing Machine . However, for our purposes, let’s consider how this classical structure is elegantly, if somewhat abstractly, transmuted for a three-tape quantum Turing machine . This specific configuration often involves one tape designated for input, a second for storing intermediate computational results, and a third for the final output.

Here’s how the elements of the classical 7-tuple are re-envisioned in the quantum domain:

• The set of states, $Q$, which in a classical machine comprises a finite collection of discrete symbols, is supplanted by a Hilbert space . This allows for a continuous spectrum of possible states, including superpositions and entangled states, a departure from the binary certitude of classical bits.
• Similarly, the tape alphabet symbols, $\Gamma$, which define the symbols that can be written on the machine’s tape, are likewise replaced by a Hilbert space . This is typically a different Hilbert space than the one used for the set of states, reflecting the distinct roles of the machine’s internal configuration versus the data it manipulates.
• The blank symbol, $b \in \Gamma$, which signifies an empty cell on the classical tape, becomes an element within this expanded tape alphabet Hilbert space , maintaining its conceptual role but existing within the quantum framework.
• The input and output symbols, $\Sigma$, conversely, are usually retained as a discrete set, much as they are in the classical system. This is a crucial practical point: neither the input provided to a quantum machine nor its eventual output necessarily needs to be a quantum system itself. This allows for interaction with classical interfaces, bridging the quantum and classical worlds.
• The transition function , $\delta: \Sigma \times Q \otimes \Gamma \to \Sigma \times Q \otimes \Gamma \times {L,R}$, which in classical computation dictates the next state, the symbol to write, and the direction of tape head movement, undergoes a profound transformation. In the quantum realm, it is conceptualized as a generalization of a semiautomaton . More concretely, it is understood to be a collection of unitary matrices . These matrices act as automorphisms of the Hilbert space $Q$, ensuring that the evolution of the quantum state is always reversible and adheres to the fundamental principles of quantum mechanics.
• The initial state, $q_0 \in Q$, which in a classical machine is a single, well-defined starting configuration, may be either a mixed state or a pure state in the quantum context. This allows for a richer and more nuanced starting point, incorporating inherent quantum uncertainty or specific prepared quantum configurations.
• Finally, the set $F$ of final or accepting states, which in classical computation defines the conditions under which a computation is considered complete and successful, is reinterpreted as a linear subspace of the Hilbert space $Q$. Acceptance in a quantum machine often involves a measurement that projects the final quantum state into this specific subspace.

It is imperative to understand that the description above serves merely as a conceptual sketch of a quantum Turing machine , rather than a truly exhaustive or formal definition. It deliberately leaves several important details somewhat ambiguous, details that, to a rigorous mind, are far from trivial. For instance, the exact timing and frequency of when a measurement is performed remains unspecified. This question of measurement profoundly impacts the operational definition of the machine, much like the distinction between a measure-once and a measure-many Quantum Finite Automaton (QFA). The precise protocol for measurement, for example, directly influences how writes to the output tape are defined and interpreted, introducing complexities that demand a more in-depth, formal treatment.

History: The Genesis of Quantum Computation

The theoretical underpinnings of quantum computation are not merely a recent fad; they trace back to foundational work in the early 1980s.

It was in 1980 and again in 1982 that the astute physicist Paul Benioff published seminal articles 5 6 that provided the very first descriptions of a quantum-mechanical model for Turing machines . His work established that a quantum system could indeed serve as a computational device, effectively demonstrating that the laws of quantum mechanics were compatible with universal computation. This was a crucial conceptual leap, showing that computation wasn’t solely the domain of classical physics.

Building upon this nascent foundation, a pivotal 1985 article penned by the brilliant Oxford University physicist David Deutsch further propelled the idea of quantum computers into the academic spotlight 4 . Deutsch’s key contribution was the explicit suggestion that quantum gates could operate in a manner analogous to traditional digital computing binary logic gates . This analogy was instrumental in conceptualizing how quantum operations, such as superposition and entanglement, could be harnessed to perform computations that were fundamentally different and potentially more powerful than their classical counterparts. He effectively laid out the blueprint for a universal quantum computer, demonstrating that any quantum computation could be decomposed into a sequence of elementary quantum operations.

More recently, researchers Iriyama, Ohya , and Volovich have taken the concept further, developing a specialized model known as the linear quantum Turing machine (LQTM). This model represents a significant generalization of the classical QTM, primarily by incorporating mixed states from the outset and, perhaps more remarkably, by allowing for irreversible transition functions. This departure from strict unitarity is particularly relevant as it permits the representation of quantum measurements without necessitating immediate classical outcomes 7 . Such a model provides a richer framework for understanding quantum processes where the classical “read-out” is not the immediate or sole focus.

In another fascinating development, a quantum Turing machine augmented with the capability of postselection was rigorously defined by the eminent computer scientist Scott Aaronson . Aaronson’s groundbreaking work demonstrated that the complexity class of problems solvable in polynomial time on such a machine, denoted as PostBQP , is precisely equivalent to the classical complexity class PP 8 . This finding offers profound insights into the theoretical limits and potential power of quantum computation under specific, albeit highly idealized, conditions, hinting at the vast, often unsettling, landscape of computational complexity.

See also

For those with an insatiable curiosity for the broader implications and applications of quantum mechanics in computation, consider exploring:

• Quantum simulator § Solving physics problems : Delving into how quantum systems themselves can be harnessed to unravel the complexities of other quantum systems, a rather meta approach to scientific inquiry.