Artificial intelligence and a universal quantum computer

Abstract

In this paper we describe a complete quantum computational model of computation that is based on the production system. The presented description of the model does not require any quantum computation background. By doing so, the reason that quantum computation may be important for pure symbolical artificial intelligence may become clear. The feature universal quantum computer based on this idea will involve programs that are related to the classical artificial intelligence programming languages such as OPS5.

Keywords

Production system tree search universal computer quantum computation

1. Introduction

In the future, there will be universal quantum computers, which will offer us new possibilities. However, these possibilities are not as ground-breaking as is sometimes believed. In addition to their being “faster” and their ability to generate true randomness, these computers will have identical computing power to a Turing machine. They will be faster because they can simultaneously encode many inputs of a problem and perform the calculation on all inputs in the time it takes to do one of the calculations classically. However, we cannot access the correct solution without additional costs. The costs are related to the number of simultaneous problems that are solved. More precisely, the costs are the square root of the number of problems that are solved in parallel. The algorithm that describes the access to a solution is called Grover’s algorithm [13–16]. Grover’s algorithm speeds up the search in an unsorted list by a quadratic factor. In a list of length n, the access costs of a solution are proportional to the square root of n $O (\sqrt{n})$ . The big O notation characterizes the computational upper-bound costs. To find an item in an unsorted list of n elements, the costs are $O (n)$ ; using Grover’s algorithm, the costs are $O (\sqrt{n})$ . The original Grover’s algorithm was probabilistic; however, it was later extended [3–5] to be fully deterministic (for example, see Section 9.4 in [28]).

Another non-trivial problem is that if we do not know exactly when a computation is finished, we cannot simply assess it. In other words, if we assess (measure) some part of the output, we also change all other possible values and spoil the computation. By assessing the value of a variable, we change the values of other variables. Because of these difficulties, quantum algorithms are described using quantum circuits. However, this method of describing an algorithm is complicated. Knowledge of parts of quantum physics and linear algebra is required. Here, the methods of AI come to our rescue, particularly the production system theory.

It should also be noted that there is an alternative method to describe the quantum computation using adiabatic quantum computation, which is based on the time evolution of a quantum system [10,11], as specified by the adiabatic theorem. It is not clear whether the adiabatic computation is more or less efficient than the computation in a classical computer [31,39]. For some problems, its efficiency can be better than the efficiency of classical computers [19,29]. There is an adiabatic quantum system called “D-Wave”, which speeds up some optimization problems [9,19,37]. This system is based on quantum annealing, which finds the global minimum of a function [6,18]. Quantum annealing attempts to avoid local minima using a quantum fluctuation parameter, which replaces a state by a randomly selected neighboring state. It is related to simulated annealing [17], where the temperature plays a quantum-fluctuation-related role. Adiabatic quantum computers based on quantum annealing do not correspond to a universal Turing machine. Instead, they are related to analog computers, where an algorithm represents a mathematical model of a physical system, and will be not discussed further in this paper.

The main contribution of this short paper is the simplification of the mathematical framework concerning a possible quantum computer and artificial intelligence. With this simplification, the main idea can be introduced to the artificial-intelligence community that has no quantum computation background. By doing so, the reason that quantum computation may be important for pure symbolical AI may become clear. The paper is organized as follows:

We review the production systems;

We introduce the tree search and path descriptors;

We review the quantum iterative deepening;

The quantum production system is presented.

2. Production system

The production system in the context of classical Artificial Intelligence and Cognitive Psychology is one of the most successful computer models of human problem solving [1,20,25,26]. A production system is composed of a set of rules [7,22]. These rules are also called productions. The set of rules models the human long-term memory and is also composed of the working memory. This memory contains a description of the state in a problem-solving process. The state is described by a string of symbols and called a set of patterns. Whenever the premise of a rule is true, the conclusions of the rules change the contents of the working memory. The working memory models the human short-term memory. During the recognize-act cycle, the current state of the problem-solving process is maintained as a set of patterns in the working memory. The working memory is initialized with the initial state description. The patterns in the working memory are matched with the premise of the rules. The premise of the rules that match the patterns in the working memory produces a set, which is called the conflict set. A rule of this set is selected, and the conclusion of the rule changes the content of the working memory. This process is denoted as firing the rule. Our production systems perform forward chaining, and only one rule is allowed to fire [22]. This recognize-cycle is repeated on the modified working memory until a goal state is attained or no rules can be fired. A problem is described by the rules in the long-term memory, the initial state, and the goal state. A chain of rules, which successively changes the state from the initial state to the goal state, represents the solution to the problem. The search, which is represented by a search tree, is performed from an initial state through the following states until a goal state is attained.

In a pure production system, which was proposed as a formal theory of computation [27], the system halts if no production can fire in a state. It is composed of the set of productions L (long-term memory) and control system C. A pure production system is a sextuple: $\begin{matrix} (1) & (Σ, L, W, γ_{i}, γ_{g}, C) \end{matrix}$ with

Σ is a finite alphabet;

W is the working memory and represents state $γ \in Σ$ ;

L is the long-term memory and the set of B productions. Production p has the form $(precondition, conclusion) \in Σ$ .

The precondition is matched with the contents of the working memory. If the precondition is met, the conclusion is preformed and changes the contents of the working memory;

$γ_{i} \in Σ$ is the initial state. The working memory is initialized with the initial state $γ_{i}$ ;

$γ_{g} \in Σ$ is the goal state;

δ is the control function of the form $Σ \to L \times Σ \times h$ . It chooses a production and fires it or halts h.

C (γ) = (p, γ^{'}, h)

, then the working memory contains symbol γ. It is substituted by production p with

γ^{'}

, or the computation halts h. The computation halts if the goal state

γ_{g}

is attained or there is an impasse (no production can be applied).

Production systems are closely related to the approach of Markov algorithms [23]; similar to these approaches, production systems are equivalent in power to a Turing machine [38]. A Turing machine can also be easily simulated by a production system; thus, a production system is a complete model of computation. The search represented by a search tree is performed from an initial state through the following states until a goal state is attained.

2.1. Tree search and the path descriptors

Nodes and edges represent a search tree. Each node represents a state, and each edge represents a transition from one state to the following state. The initial state defines the root of the tree. From each state, either B states can be reached, or the state is a leaf. B represents the branching factor of the node. A leaf represents either the goal of the computation or an impasse when there is no valid transition to a succeeding state. Every node besides the root has a unique node from which it was reached, which is called the parent. Each node and its parent are connected by an edge. Each parent has B children. If $B = 2$ , each of m questions has a reply of either “yes” or “no” and can be represented by a bit (see Fig. 1). The m answers are represented by a binary number of length m. There are $n = 2^{m} = B^{m}$ possible binary numbers of length m. Each binary number represents a path from the root to a leaf. For each goal, a certain binary number indicates the solution. For a constant branching factor $B > 2$ , each question has B possible answers. The m answers can be represented by a base-B number with m digits. For example, with $B = 8$ , the number is represented in an octal numeral system. These numbers represent all paths from the root to the leaves.

Fig. 1.

Search tree for $B = 2$ and $m = 2$ . Each question can be represented by a bit. Each binary number (11, 10, 01, 00) represents a path from the root to the leaf.

2.2. Quantum iterative deepening

In a quantum computation, we can simultaneously represent all possible path descriptors. There is one path descriptor for each leaf of the tree. Using Grover’s algorithm, we search through all possible paths and verify whether each path leads to the goal state. This type of procedure is called a quantum tree search [33]. For $n = B^{m}$ possible paths, the costs are $O (\sqrt{n}) = O (\sqrt{B^{\frac{m}{2}}})$ . A constraint of this approach is that we must know the depth m of the search tree in advance. The constraint can be overcome by iterative deepening. In an iterative deepening search, we gradually increase the limit of the search from one to two to three to four and continue to do so until a goal is found. For each limit, a search is performed from the root to the maximum depth of the search tree. During the iterative deepening search, the states are generated multiple times [21,30]. The time complexity of the iterative deepening search is of the same order of magnitude as a search to the maximum depth [21], as explained by Richard E. Korf: “Since the number of nodes on a given level of the tree grows exponentially with depth, almost all time is spent in the deepest level, even through shallower levels are generated an arithmetically increasing number of times.” The paradox can be explained using the arithmetic–geometric sequence. A quantum iterative deepening search is equivalent to the iterative deepening search [34,36]. For each limit max, a quantum tree search is performed from the root, where max is the maximum depth of the search tree. The possible solutions are determined using a measurement. The time complexity of an iterative deepening search has the same order of magnitude as the quantum tree search with $\begin{matrix} (2) & O (1) + O (B^{\frac{1}{2}}) + \dots + O (B^{\frac{m}{2}}) = O (B^{\frac{m}{2}}) \end{matrix}$ according to the arithmetic–geometric sequence. A second constraint is represented by the constant branching factor. If the branching factor is not constant, the maximal branching factor $B_{max}$ must be used for the quantum tree search [33].

3. A quantum production system

A quantum production system is based on the iterative quantum tree search. In an iterative quantum tree search, the limit is gradually increased in each step. For each limit, a quantum tree search is performed [34,36]. A quantum production system is composed of the quantum oracle $L_{t} (γ_{i}, γ_{g}, d (t))$ and Grover’s algorithm [32,35]. A quantum oracle marks a solution among all n possible values if there is a solution. Grover’s algorithm enables us to see (measure) the marked solution. A quantum production system is an instantiation of the sextuple $(Σ, L_{t} (γ_{i}, γ_{g}, d (t)), d (t), t, γ_{i}, γ_{g})$ with

Σ is a finite alphabet;

The quantum oracle $L_{t} (γ_{i}, γ_{g}, d (t))$ recognizes solutions to the search problem of depth t for given path descriptor, initial state and goal state. It marks the solution if there is a solution;

$d (t)$ is the path descriptor with limit t; for branching factor B. There are $n = B^{t}$ possible $d_{i} (t)$ paths;

t is the depth of the corresponding search tree;

$γ_{i} \in Σ$ is the initial state. The working memory is initialized with the initial state $γ_{i}$ ;

$γ_{g} \in Σ$ is the goal state.

Each path descriptor represents a possible path from the root to the leaf $d_{i} (t)$ with limit t. During the quantum computation, a superposition over all possible paths to depth t is built. A superposition indicates that we simultaneously encode many inputs and can perform the calculation on all inputs in the time it takes to do one of the calculations classically. For the branching factor B, there are $n = B^{t}$ possible $d_{i} (t)$ paths; the index i ranges from 1 to n. The quantum oracle $L_{t} (γ_{i}, γ_{g}, d (t))$ verifies in parallel whether each path that is specified by the path descriptor $d_{i} (t)$ corresponds to a sequence of productions, which leads from the initial state to the goal state. It marks the solution if there is a solution. Grover’s algorithm is performed, and we assess the output (a measurement is performed). Grover’s algorithm ensures that we measure the solution if it exists. If there is a solution for $n = B^{t}$ possible $d_{i} (t)$ paths, the superposition of the path descriptors is projected onto the path descriptor $d_{solution} (t)$ , which we can assess. The costs are $O (\sqrt{n}) = O (\sqrt{t^{m}})$ . A quantum oracle marks a solution among all n possible values if there is a solution. Grover’s algorithm with the suggested modifications [4,5] is fully deterministic in the case of a marked solution. If no solution is marked, we obtain a random path description, which indicates that there is no solution. If there is no solution, then $t = t + 1$ , new quantum oracle $L_{t + 1} (γ_{i}, γ_{g}, d (t + 1))$ is built, a new superposition over all possible paths to depth $t + 1$ is built, and the entire procedure is repeated. The quantum oracle $L_{t + 1} (γ_{i}, γ_{g}, d (t + 1))$ can be (automatically) built using quantum circuit because the production system, which is described by each path descriptor $d_{i} (t)$ , is deterministic and reversible. For example, a NOT gate is reversible in the sense that one can infer the output from the input. However, neither the AND or the OR gates is reversible because one cannot infer the output from the input. To build such a quantum oracle, we store each rule with the corresponding descriptor (digit). For a branching factor of 2, the descriptor is 0 or 1; the path of the descriptor is represented by the binary number. For further details, please consult [33] and [34].

3.1. Grover’s algorithm

A superposition corresponds to a vector of dimension n, where each dimension corresponds to a path description. For example, in Fig. 1, the dimension of the vector is four, and each dimension corresponds to the binary number that represents the path descriptor plus one, starting with dimension one, two and three and four (path descriptor zero corresponds to dimension one). Each dimension is described by a complex number (also called amplitude) $ω_{i}$ with the constraint that the Euclidean length of the vector is always one. For the example in Fig. 1, the four-dimensional vector s is given by $\begin{matrix} (3) & s = (\begin{matrix} ω_{0} \\ ω_{1} \\ ω_{2} \\ ω_{3} \end{matrix}) \end{matrix}$ with $\begin{matrix} (4) & 1 = ‖ s ‖ . \end{matrix}$ Because the length of the vectors must always be one, all operators that manipulate the vector must be length preserving. It should be noted that the length-preserving operators describe a reversible computation. In quantum computation, the operators are described using square matrices. Length-preserving matrices for complex numbers are unitary matrices, whose conjugate transposes are equal to their inverse, $\begin{matrix} (5) & U^{*} = U^{- 1} . \end{matrix}$ The real analogue of a unitary matrix is an orthogonal matrix. Now, if we measure this vector, the probabilities that the system will be found in the first dimension that corresponds to the binary path descriptors zero, one, two and three are $| ω_{0} |^{2}$ , $| ω_{1} |^{2}$ , $| ω_{2} |^{2}$ and $| ω_{3} |^{2}$ , respectively. This result follows from the requirement that the length of the vector is one. In addition, the product of a complex number with its conjugate is always a real number, $\begin{matrix} (6) & ω^{*} \cdot ω = (x - y \cdot i) \cdot (x + y \cdot i) = x^{2} + y^{2} = | ω |^{2} . \end{matrix}$ Before we start the computation, the amplitudes are evenly distributed, $\begin{matrix} (7) & s = (\begin{matrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{matrix}) \end{matrix}$ each corresponding to the probability $0.25 = | 0.5 |^{2}$ . A quantum oracle marks the solution by a negative sign, in our example it is the path descriptor one. Actually this process is more complicated and only as a result of some transformations the amplitude becomes negative [28,40], $\begin{matrix} (8) & s = (\begin{matrix} 0.5 \\ - 0.5 \\ 0.5 \\ 0.5 \end{matrix}) . \end{matrix}$ The Grover’s iterate that is based on Householder reflection described by an unitary matrix amplifies the amplitude into $\begin{matrix} (9) & s = (\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix}) \end{matrix}$ and a measurement indicates the path descriptor one. For dimensions higher than four ( $4 ≪ n$ ), the operations of marking and Householder reflection must be repeated $O (\sqrt{n})$ times. Each operation is called a Grover’s iterate. In honor of its inventor, the Indian-American computer scientist Lov Kumar Grover, the algorithm is named Grover’s algorithm. Grover’s algorithm with the suggested modifications [3–5,28] indicates the path descriptor after $O (\sqrt{n})$ if there is a path descriptor.

3.2. Complete model of computation

The result of the computation is represented by a path descriptor (Fig. 1). After each iterative step, Grover’s algorithm is performed. If no goal is reached, the limit of the search is increased, and the procedure is repeated. If the goal state can be reached, the corresponding path descriptor is accessed by Grover’s algorithm. Because a Turing machine can also be easily simulated using a quantum production system and a pure production system, and because we can map a pure production system into a quantum production system, the iterative quantum production system is a complete computation model [36].

4. Discussion

The Turing machine is a theoretical mathematical model created by Alan Turing [38]. We relate a Turing machine to a possible definition of a quantum Turing machine and indicate the resulting problems.

4.1. Classical Turing machines

The Turing machine constitutes an infinitely long tape that is divided into a sequence of cells. In each cell, a certain symbol can be written and later read by a head. The head can move along the tape and exist in one state of a finite set of internal states. A set of rules specifies a new state given the current state and the symbol being read. The new state determines in which direction the head must move and if it must write or read a symbol. For each state, only one rule describes one action. Formally a Turing machine is a 7-tuple: $\begin{matrix} (10) & (Q, Γ, b, Σ, δ, γ_{i}, γ_{g}) \end{matrix}$ with

Q finite, non-empty set of states;

Γ is a finite, non-empty set of tape alphabet symbols;

$b \in Γ$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation);

$Σ \subseteq Γ ∖ {b}$ is the set of input symbols;

$δ : (Q ∖ F) \times Γ \to Q \times Γ \times {L, R}$ is a the transition function, where L is left shift, R is right shift;

$γ_{i} \in Q$ is the initial state;

$γ_{g} \subseteq Q$ is the set of halt states. The initial tape contents is said to be accepted by Turing machine if it halts in a state from $γ_{g}$ .

Turing realized that one could encode the transformation rules of any specific Turing machine T as some pattern of symbols on the tape that fed into a special Turing machine

UT

UT

had the effect of reading in the pattern, specifying the transformation rules for T and then simulating T. Any algorithmic process can be simulated on a Turing machine

UT

. Entscheidungsproblem corresponds to the halting problem. Whether a program will halt or run forever can be determined and is based on the given program with a finite input.

The elegant way of modeling a computer by a Turing machine leads us to computational complexity theory. Computational complexity theory addresses the questions of which problems can be solved in a finite amount of time on a computer. The definition of computational complexity should not depend upon the currently used computational model. The following is stated in the Church–Turing thesis: Any algorithmic process can be simulated on a Turing machine. The extended Church–Turing thesis, which is also called the strong Church–Turing thesis, states that everything that can be computed in a certain amount of time on any physical computer can be also be computed on a Turing machine with a polynomial slowdown. In other words, any reasonable algorithmic process can be simulated on a Turing machine, with the possibility of a polynomial slowdown, in the number of steps required to run the simulation.

However Richard Feynman observed in the early eighties that it did not appear possible for a Turing machine to simulate certain quantum physical processes without incurring an exponential slowdown. This fact would contradict the strong Church–Turing thesis, which led Feynman to ask whether a quantum system can be simulated on an imaginary quantum computer.

4.2. Quantum Turing machines

In 1985, David Deutsch [8] reformulated the Church–Turing thesis based on the observation of Richard Feynman in physical terms: “Every finitely realizable physical system can be perfectly simulated by universal computing machine operating by finite means.” The Turing machine was replaced by the universal computing machine which operates by finite means. Such a universal computing machine that operates by finite means could be modeled by a quantum Turing machine first proposed by David Deutsch [8]. A quantum Turing is a 7-tuple as before $\begin{matrix} (11) & (Q, Γ, b, Σ, δ, γ_{i}, γ_{g}), \end{matrix}$ however the states are represented corresponding vectors and the transition function δ is represented by unitary matrices. In classical models such as the Turing machine, the end of a calculation is indicated by a halt state. An observer must check if the calculation halted. In a quantum Turing machine, a halt flag corresponding to $γ_{g}$ can be non-trivially implemented due to entanglement and the collapse of the halt qubit after the measurement. A solution to this problem is a universal quantum Turing machine in [2], which does not incorporate into its definition the concept on non-termination. Myers in [24] argues that the models presented in [8] and [2] are not truly universal because they do not allow for non-terminating computation. Also the definition of the quantum speed up is not incorporated into the description of a quantum Turing machine.

5. Conclusion

Quantum production system can operate independently of whether the computation terminates; in the case of non-termination, the computation continues forever, and the iterations do not terminate. The quantum production system also provides a maximal speedup of $O (\sqrt{n})$ if the Turing machine simulation allows n multiple computational branches [36].

A quantum computer based on a quantum production system will involve classical artificial-intelligence programing languages, such as OPS5 [7]. OPS5 programs are executed by matching the working memory elements with productions in the long-term memory [12]. Thus, the programmer is not required to contend with quantum gates, nor is he or she required to address the principles of quantum computation. It is equivalent to current programmers who specify their algorithms in high-level languages, such as Java, without the requirement of understanding the nature of electronic circuits or semiconductor devices, such as a transistor.

For more background information see these additional sources [32,35,36] and [40].

References

Anderson, The Architecture of Cognition, Harvard Univ. Press, 1983.

Bernstein and

Vazirani, Quantum complexity theory, in: STOC’93: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, 1993, pp. 11–20.

Boyer,

Brassard,

Hoeyer and

Tapp, Tight bounds on quantum searching, Fortschritte der Physik 46 (1998), 493–505.

Brassard,

Hoyer,

Mosca and

Tapp, Quantum amplitude amplification and estimation, May 2000, available at: arXiv:quant-ph/0005055.

Brassard,

Hoyer and

Tapp, Quantum Counting, 1998.

Brooke,

Bitko,

Rosenbaum and

Aeppli, Quantum annealing of a disordered magnet, Science 284(5415) (1999), 779–781.

Brownston,

Farell,

Kant and

Martin, Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming, Addison-Wesley, 1985.

Deutsch, Quantum theory, the Church–Turing principle and the universal quantum computer, Proceedings of the Royal Society of London – Series A, Mathematical and Physical Sciences 400 (1985), 97–117.

DiCarlo,

M.D.

Reed,

Sun,

B.R.

Johnson,

J.M.

Chow,

J.M.

Gambetta,

Frunzio,

S.M.

Girvin,

M.H.

Devoret and

R.J.

Schoelkopf, Preparation and measurement of three-qubit entanglement in a superconducting circuit, Nature 467(7315) (2010), 574–578.

10.

Farhi,

Goldstone,

Gosset,

Gutmann,

H.B.

Meyer and

Shor, Quantum adiabatic algorithms, small gaps, and different paths, 2009, available at: arXiv:0909.4766.

11.

Farhi,

Goldstone,

Gutmann and

Sipser, Quantum computation by adiabatic evolution, January 2000, available at: arXiv:quant-ph/0001106.

12.

Forgy, OPS5 user’s manual CMU-CS-81-135, Technical report, Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA, USA, 1981.

13.

L.K.

Grover, A fast quantum mechanical algorithm for database search, in: STOC’96: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, 1996, pp. 212–219.

14.

L.K.

Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79 (1997), 325–328.

15.

L.K.

Grover, A framework for fast quantum mechanical algorithms, in: STOC’98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, USA, 1998, pp. 53–62.

16.

L.K.

Grover, Quantum computers can search rapidly by using almost any transformation, Phys. Rev. Lett. 80(19) (1998), 4329–4332.

17.

Hertz,

Krogh and

R.G.

Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, 1991.

18.

M.W.

Johnson,

M.H.S.

Amin,

Gildert,

Lanting,

Hamze,

Dickson,

Harris,

A.J.

Berkley,

Johansson,

Bunyk,

E.M.

Chapple,

Enderud,

J.P.

Hilton,

Karimi,

Ladizinsky,

Oh,

Perminov,

Rich,

M.C.

Thom,

Tolkacheva,

C.J.S.

Truncik,

Uchaikin,

Wang,

Wilson and

Rose, Quantum annealing with manufactured spins, Nature 473(7346) (2011), 194–198.

19.

Karimi,

N.G.

Dickson,

Hamze,

M.H.S.

Amin,

Drew-Brook,

F.A.

Chudak,

P.I.

Bunyk,

W.G.

Macready and

Rose, Investigating the performance of an adiabatic quantum optimization processor, June 2010, available at: arXiv:1006.4147.

20.

Klahr and

Waterman, Expert Systems: Techniques, Tools and Applications, Addison-Wesley, 1986.

21.

R.E.

Korf, Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence 27(1) (1985), 97–109.

22.

G.F.

Luger and

W.A.

Stubblefield, Artificial Intelligence, Structures and Strategies for Complex Problem Solving, 3rd edn, Addison-Wesley, 1998.

23.

Markov, The Theory of Algorithms, National Academy of Sciences, USSR, 1954.

24.

J.M.

Myers, Can a universal quantum computer be fully quantum?, Phys. Rev. Lett. 78(9) (1997), 1823–1824.

25.

Newell, Unified Theories of Cognition, Harvard Univ. Press, 1990.

26.

Newell and

Simon, Human Problem Solving, Prentice Hall, 1972.

27.

Post, Formal reductions of the general combinatorial problem, American Journal of Mathematics 65 (1943), 197–268.

28.

Rieffel and

Polak, Quantum Computing – A Gentle Introduction, MIT Press, 2011.

29.

Roland and

N.J.

Cerf, Quantum search by local adiabatic evolution, Phys. Rev. A 65 (2002), 042308.

30.

Russell and

Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall Series in Artificial Intelligence, Prentice Hall, 2010.

31.

Tarrataca, Challenges of adiabatic quantum evaluation of NAND trees, Quantum Information Processing 14(12) (2015), 4731–4749.

32.

Tarrataca and

Wichert, Problem-solving and quantum computation, Cognitive Computation 3 (2011), 510–524.

33.

Tarrataca and

Wichert, Tree search and quantum computation, Quantum Information Processing 10(4) (2011), 475–500. doi:10.1007/s11128-010-0212-z.

34.

Tarrataca and

Wichert, Iterative quantum tree search, in: CiE 2012 – How the World Computes, 2012.

35.

Tarrataca and

Wichert, A quantum production model, Quantum Information Processing 11(1) (2012), 189–209. doi:10.1007/s11128-011-0231-4.

36.

Tarrataca and

Wichert, Quantum iterative deepening with an application to the halting problem, PLoS ONE 8(3) (2013), e57309.

37.

Tay,

Loo and

Perus, Face recognition with quantum associative networks using overcomplete Gabor wavelet, Cognitive Computation 2(4) (2010), 297–302. doi:10.1007/s12559-010-9047-2.

38.

Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 2 (1936), 260–265.

39.

van Dam and

Vazirani, Limits on quantum adiabatic optimization, in: 5th Workshop on Quantum, 2001.

40.

Wichert, Principles of Quantum Artificial Intelligence, World Scientific, 2013.