This paper extends work done to date on quantum computation by association of potentials with different types of steps. Quantum Turing machine Hamiltonians, generalized to include potentials, correspond to sums over tight binding Hamiltonians each with a different potential distribution. Which distribution applies is determined by the initial state. An example, which enumerates the integers in succession as binary strings, is analyzed. It is seen that for some initial states, the potential distributions have quasicrystalline properties and are similar to a substitution sequence.
Quantum Turing machines are discussed and reviewed in this paper. Most of the paper is concerned with processes defined by a step operator T that is used to construct a Hamiltonian H according to Feynman's prescription. Differences between these models and the models of Deutsch are discussed and reviewed. It is emphasized that the models with H constructed from T include fully quantum mechanical processes that take computation basis states into linear superpositions of these states. The requirement that T be distinct path generating is reviewed. The advantage of this requirement is that Schrödinger evolution under H is one dimensional along distinct finite or infinite paths of nonoverlapping states in some basis BT. It is emphasized that BT can be arbitrarily complex with extreme entanglements between states of component systems. The new aspect of quantum Turing machines introduced here is the emphasis on the structure of graphs obtained when the states in the BT paths are expanded as linear superpositions of states in a reference basis such as the computation basis BC. Examples are discussed that illustrate the main points of the paper. For one example the graph structures of the paths in BT expanded as states in BC include finite stage binary trees and concatenated finite stage binary trees with or without terminal infinite binary trees. Other examples are discussed in which the graph structures correspond to interferometers and iterations of interferometers. 03.65.Bz,89.70.+c
Here the results of other work on quantum mechanical Hamiltonian models of Turing machines are extended to include any discrete process T on a countably infinite set A. The models are constructed here by use of scattering phase shifts from successive scatterers to turn on successive step interactions. Also a locality requirement is imposed. The construction is done by first associating with each process T a model quantum system M with associated Hilbert space ℋM and step operator UT. Since UT is not unitary in general, M, ℋM, and UT are extended into a (continuous time) Hamiltonian model on a larger space which satisfies the locality requirement. The construction is compared with the minimal unitary dilation of UT. It is seen that the model constructed here is larger than the minimal one. However, the minimal one does not satisfy the locality requirement.
Contrary to the classical case, the relation between quantum programming languages and quantum Turing Machines (QTM) has not been fully investigated. In particular, there are features of QTMs that have not been exploited, a notable example being the intrinsic infinite nature of any quantum computation. In this paper, we propose a definition of QTM, which extends and unifies the notions of Deutsch and Bernstein & Vazirani. In particular, we allow both arbitrary quantum input, and meaningful superpositions of computations, where some of them are “terminated” with an “output”, while others are not. For some infinite computations an “output” is obtained as a limit of finite portions of the computation. We propose a natural and robust observation protocol for our QTMs, which does not modify the probability of the possible outcomes of the machines. Finally, we use QTMs to define a class of quantum computable functions—any such function is a mapping from a general quantum state to a probability distribution of natural numbers. We expect that our class of functions, when restricted to classical input-output, will not be different from the set of the recursive functions.
A goal of quantum-mechanical models of the computation process is the description of operators that model changes in the information-bearing degrees of freedom. Iteration of the operators should correspond to steps in the computation, and the final state of halting computations should be stable under iteration. The problem is that operators constructed directly from the process description do not have these properties. In general these operators annihilate the halted state. If information-erasing steps are present, there are additional problems. These problems are illustrated in this paper by consideration of operators for two simple one-step processes and two simple Turing machines. In general the operators are not unitary and, if erasing steps are present, they are not even contraction operators. Various methods of extension or dilation to unitary operators are discussed. Here unitary power dilations are considered as a solution to these problems. It is seen that these dilations automatically provide a good solution to the initial- and final-state problems. For processes with erasing steps, recording steps must be included prior to the dilation, but only for the steps that erase information. Hamiltonians for these processes are also discussed. It is noted that H, described by exp(-iH\ensuremath{\Delta})=
UT, where
UT is a unitary step operator for the process and \ensuremath{\Delta} a time interval, has complexity problems. These problems and those noted above are avoided here by the use of the Feynman approach to constructing Hamiltonians directly from the unitary power dilations of the model operators. It is seen that the Hamiltonians so constructed have some interesting properties.
We present results on quantum Turing machines and on prover-verifier interactions. \n \n \nIn our work on quantum Turing machines, we continue the line of research opened by Yao (1993), who proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We then first revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t, rather than quadratic depth, and can be extended easily to many variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of a method of Arrighi, Nesme, and Werner (2011) that allows for the localization of causal unitary evolutions, involving abstract lemmas that might be of independent interest. \n \n \nWe also consider the more complex extension of our variant to the circuit simulation of multi-tape quantum Turing machines, where our variant provides a circuit with O(t^k) size and O(t^{k-1}) depth for the simulation of t steps of a machine with k tapes. This can be contrasted with the O(t^{k}) depth corresponding to the generalization of Yao's simulation by Nishimura and Ozawa (2002). Our usage of abstract techniques regarding the localization of causal unitary evolutions allows again for a simplification of the algebraic manipulation aspects of the construction. We also discuss the further extension to the case of oracle quantum Turing machines. \n \n \nIn our work on prover-verifier interactions, we first consider a protocol under the name of perfect/conclusive quantum state exclusion. This means to be able to discard with certainty at least one out of n possible quantum state preparations by performing a measurement of the resulting state. When all the preparations correspond to pure states and there are no more of them than their common dimension, it is an open problem whether POVMs give any additional power for this task with respect to projective measurements. This is the case even for the simple case of three states in three dimensions, which is discussed by Caves, Fuchs and Schack (2002) as unsuccessfully tackled. In our work, we give an analytical proof that in this case POVMs do indeed not give any additional power with respect to projective measurements. We also discuss possible generalizations of our work, including an application of Quadratically Constrained Quadratic Programming that might be of special interest. \n \n \nWe additionally consider the problem of quantum hedging, a particular kind of quantum correlation that arises between parallel instances of prover-verifier interactions. M. and Watrous (2012) studied a protocol that exhibited a perfect form of quantum hedging, where the risk for the prover of losing a first game can completely offset the corresponding risk for a second game. We take a step towards a better understanding of this hedging phenomenon by giving a characterization of the prover's optimal behavior for a natural generalization of this protocol. Furthermore, we discuss how the usage of the logarithmic utility principle to analyze prover-verifier interactions could justify further study of quantum hedging.
As was well known, in classical computation, Turing machines, circuits, multi-stack machines, and multi-counter machines are equivalent, that is, they can simulate each other in polynomial time. In quantum computation, Yao [11] first proved that for any quantum Turing machines
M, there exists quantum Boolean circuit
(n,t)-simulating
M, where
n denotes the length of input strings, and
t is the number of move steps before machine stopping. However, the simulations of quantum Turing machines by quantum multi-stack machines and quantum multi-counter machines have not been considered, and quantum multi-stack machines have not been established, either. Though quantum counter machines were dealt with by Kravtsev [6] and Yamasaki {\it et al.} [10], in which the machines count with
0,±1 only, we sense that it is difficult to simulate quantum Turing machines in terms of this fashion of quantum computing devices, and we therefore prove that the quantum multi-counter machines allowed to count with
0,±1,±2,...,±n for some
n>1 can efficiently simulate quantum Turing machines. Therefore, our mail goals are to establish quantum multi-stack machines and quantum multi-counter machines with counts
0,±1,±2,...,±n and
n>1, and particularly to simulate quantum Turing machines by these quantum computing devices.