Quantum computation is a subject of much recent interest. In much of the work in the literature quantum computers are described as built up from a sequence of unitary operators where each unitary operator carries out a stage of the overall quantum computation. The sequence and connection of the different unitary operators is provided presumably by some external agent which governs the overall process. However there is no description of a an overall Hamiltonian needed to give the actual quantum dynamics of the computation process. In this talk, earlier work by the author is followed in that simple, time independent Hamiltonians are used to describe quantum computation, and the Schroedinger evolution of the computation system is considered to be quantum ballistic. However, the definition of quantum ballistic evolution used here is more general than that used in the earlier work. In particular, the requirement that the step operator {ital T} associated with a process be a partial isometry, used in, is relaxed to require that {ital T} be a contraction operator. (An operator {ital T} is a partial isometry if the self-adjoint operators T{sup {dagger}}T and TT{sup {dagger}} are also projection operators.{ital T} is a contraction operator if {vert_bar}{vert_bar} {ital T} {vert_bar}{vert_bar} {<=} 1.) The main purpose of this talk is to investigate some consequences for quantum computation under this weaker requirement. It will be seen that system motion along discrete paths in a basis still occurs. However the motion occurs in ,the presence of potentials whose height and distribution along the path depends on {ital T} and the path states.
Quantum computation is a subject of much recent interest. In much of the work in the literature quantum computers are described as built up from a sequence of unitary operators where each unitary operator carries out a stage of the overall quantum computation. The sequence and connection of the different unitary operators is provided presumably by some external agent which governs the overall process. However there is no description of a an overall Hamiltonian needed to give the actual quantum dynamics of the computation process. In this talk, earlier work by the author is followed in that simple, time independent Hamiltonians are used to describe quantum computation, and the Schroedinger evolution of the computation system is considered to be quantum ballistic. However, the definition of quantum ballistic evolution used here is more general than that used in the earlier work. In particular, the requirement that the step operator {ital T} associated with a process be a partial isometry, used in, is relaxed to require that {ital T} be a contraction operator. (An operator {ital T} is a partial isometry if the self-adjoint operators T{sup {dagger}}T and TT{sup {dagger}} are also projection operators.{ital T} is a contraction operator if {vert_bar}{vert_bar} {ital T} {vert_bar}{vert_bar} {<=} 1.) The main purpose of this talk is to investigate some consequences for quantum computation under this weaker requirement. It will be seen that system motion along discrete paths in a basis still occurs. However the motion occurs in ,the presence of potentials whose height and distribution along the path depends on {ital T} and the path states.
Quantum computers are important examples of processes whose evolution can be described in terms of iterations of single-step operators or their adjoints. Based on this, Hamiltonian evolution of processes with associated step operators T is investigated here. The main limitation of this paper is to processes which evolve quantum ballistically, i.e., motion restricted to a collection of nonintersecting or distinct paths on an arbitrary basis. The main goal of this paper is proof of a theorem which gives necessary and sufficient conditions that T must satisfy so that there exists a Hamiltonian description of quantum ballistic evolution for the process, namely, that T is a partial isometry and is orthogonality preserving and stable on some basis. Simple examples of quantum ballistic evolution for quantum Turing machines with one and with more than one type of elementary step are discussed. It is seen that for nondeterministic machines the basis set can be quite complex with much entanglement present. It is also proven that, given a step operator T for an arbitrary deterministic quantum Turing machine, it is decidable if T is stable and orthogonality preserving, and if quantum ballistic evolution is possible. The proof fails if T is a step operator for a nondeterministic machine. It is an open question if such a decision procedure exists for nondeterministic machines. This problem does not occur in classical mechanics. Also the definition of quantum Turing machines used here is compared with that used by other authors. \textcopyright{} 1996 The American Physical Society.
Discrete-time quantum walks provide a universal model of computation, meaning that any computation done by a general purpose quantum computer can also be done by discrete-time quantum walks. In the last decades great progress has been done in this field, developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the mapping from one model to the other is an open problem, thus as an attempt to address this problem, we in this work develop basic theory, experiments and simulations on quantum walks presented in the following way: In the first part of this work we provide a matrix analysis of the evolution operator of Unitary Coined Discrete-Time Quantum Walks (UCDTQW), which leads to the fact that any quantum circuit applied on a bipartite system can be considered as the shift operator of a UCDTQW, and vice versa. Furthermore, we show that the fact that the statevector associated to a quantum walker in a UCDTQW is a bipartite system, inherits the evolution operator the property to be a block matrix, where each block is a Kraus operator. We show that associated to the shift operator of any UCDTQW, there exists a directed multigraph on which the walker moves, thus mimicking the functionality of the transition matrix in a random walk. We also extend the definition of the coin operator in a UCDTQW to a superposition of coins that act on different vertices of the graph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. In the second part of this work, we study the mapping of evolution operators to the quantum circuit model, based on a special case when the shift operator has a block diagonal matrix representation. In this case we propose a mapping process that is straightforward, and apply this method to obtain quantum circuits that generate UCDTQW on the most common topologies found in the literature: the straight line, the cyclic graph, the hypercube and the complete graph. In view that the mapping is not unique, we provide different models for the some topologies, along with techniques to synthesize them. The obtained circuits were implemented on IBM’s quantum computers through the Quantum Composer platform, obtaining mixed results for the different models, but being the circuit associated to the complete graph the one with best performance. Finally, in the third part of this work, we use the theoretical framework proposed in the first two parts to analyze and modify a quantum walk-based search algorithm which proposed over 20 years ago, and then execute it for the first time on a general-purpose quantum computer provided by IBM.
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
We have seen how information can be encoded onto a quantum system by selecting the state in which it is prepared. Retrieving the information is achieved by performing a measurement, and the optimal measurement in any given situation is usually a generalized measurement. In between preparation and measurement, the information resides in the quantum state of the system, which evolves in a manner determined by the Hamiltonian. The associated unitary transformation may usefully be viewed as quantum information processing; if we can engineer an appropriate Hamiltonian then we can use the quantum evolution to assist in performing computational tasks. Our objective in quantum information processing is to implement a desired unitary transformation. Typically this will mean coupling together a number, perhaps a large number, of qubits and thereby generating highly entangled states. It is fortunate, although by no means obvious, that we can realize any desired multiqubit unitary transformation as a product of a small selection of simple transformations and, moreover, that each of these need only act on a single qubit or on a pair of qubits. The situation is reminiscent of digital electronics, in which logic operations are decomposed into actions on a small number of bits. If we can realize and control a very large number of such operations in a single device then we have a computer. Similar control of a large number of qubits will constitute a quantum computer. It is the revolutionary potential of quantum computers, more than any other single factor, that has fuelled the recent explosion of interest in our subject. We shall examine the remarkable properties of quantum computers in the next chapter. In digital electronics, we represent bit values by voltages: the logical value 1 is a high voltage (typically +5 V) and 0 is the ground voltage (0 V). The voltage bits are coupled and manipulated by transistor-based devices, or gates. The simplest gates act on only one bit or combine two bits to generate a single new bit, the value of which is determined by the two input bits. For a single bit, with value 0 or 1, the only possible operations are the identity (which does not require a gate) and the bit flip.
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.
Given a quantum Hamiltonian and its evolution time, the corresponding unitary evolution operator can be constructed in many different ways, corresponding to different trajectories between the desired end-points and different series expansions. A choice among these possibilities can then be made to obtain the best computational complexity and control over errors. It is shown how a construction based on Grover's algorithm scales linearly in time and logarithmically in the error bound, and is exponentially superior in error complexity to the scheme based on the straightforward application of the Lie–Trotter formula. The strategy is then extended first to simulation of any Hamiltonian that is a linear combination of two projection operators, and then to any local efficiently computable Hamiltonian. The key feature is to construct an evolution in terms of the largest possible steps instead of taking small time steps. Reflection operations and Chebyshev expansions are used to efficiently control the total error on the overall evolution, without worrying about discretization errors for individual steps. We also use a digital implementation of quantum states that makes linear algebra operations rather simple to perform.