Algebraic random walks (ARW) and quantum mechanical random walks (QRW) are investigated and related. Based on minimal data provided by the underlying bialgebras of functions defined on e. g the real line R, the abelian finite group Z_N, and the canonical Heisenberg-Weyl algebra hw, and by introducing appropriate functionals on those algebras, examples of ARWs are constructed. These walks involve short and long range transition probabilities as in the case of R walk, bistochastic matrices as for the case of Z_N walk, or coherent state vectors as in the case of hw walk. The increase of classical entropy due to majorization order of those ARWs is shown, and further their corresponding evolution equations are obtained. Especially for the case of hw ARW, the diffusion limit of evolution equation leads to a quantum master equation for the density matrix of a boson system interacting with a bath of quantum oscillators prepared in squeezed vacuum state. A number of generalizations to other types of ARWs and some open problems are also stated. Next, QRWs are briefly presented together with some of their distinctive properties, such as their enhanced diffusion rates, and their behavior in respect to the relation of majorization to quantum entropy. Finally, the relation of ARWs to QRWs is investigated in terms of the theorem of unitary extension of completely positive trace preserving (CPTP) evolution maps by means of auxiliary vector spaces. It is applied to extend the CPTP step evolution map of a ARW for a quantum walker system into a unitary step evolution map for an associated QRW of a walker+quantum coin system. Examples and extensions are provided.
Using the known possibility to associate the completely positive maps with density matrices and recent results on expressing the density matrices with sets of classical probability distributions of dichotomic random variables we construct the probability representation of the completely positive maps. In this representation, any completely positive map of qubit state density matrix is identified with the set of classical coin probability distributions. Examples of the maps of qubit states are studied in detail. The evolution equation of quantum states is written in the form of the classical-like kinetic equation for probability distributions identified with qubit state.
Hopf algebras of functions and operators are utilized to develop a mathematical construction scheme for building algebraic random walks. The main construction treats systems of covariance formed by translation operator and its associated operator valued measures on e.g. the circle and the line, and derives an algebraic quantum random walk by means of completely positive trace preserving maps. Asymptotic limit of the action of such maps is shown to lead to quantum master equations of Lindblad type. 2000 MSC: 57T05, 60B15, 81R15
Classical random walks and Markov processes are easily described by Hopf algebras. It is also known that groups and Hopf algebras (quantum groups) lead to classical and quantum diffusions. We study here the more primitive notion of a quantum random walk associated with a general Hopf algebra and show that it has a simple physical interpretation in quantum mechanics. This is by means of a representation theorem motivated from the theory of Kac algebras: If H is any Hopf algebra, it may be realized in Lin(H) in such a way that Δh=W(h⊗1)W−1 for an operator W. This W is interpreted as the time evolution operator for the system at time t coupled quantum-mechanically to the system at time t+δ. Finally, for every Hopf algebra there is a dual one, leading us to a duality operation for quantum random walks and quantum diffusions and a notion of the coentropy of an observable. The dual system has its time reversed with respect to the original system, leading us to a novel kind of CTP theorem.
We discuss a new approach to simulate quantum algorithms using classical probabilistic bits and circuits. Each qubit (a two-level quantum system) is initially mapped to a vector in an eight dimensional probability space (equivalently, to a classical random variable with eight probabilistic outcomes). The key idea in this mapping is to store both the amplitude and phase information of the complex coefficients that describe the qubit state in the probabilities. Due to the identical tensor product structure of combining multiple quantum systems as well as multiple probability spaces,
n qubits are then mapped to a tensor product of
n 8-dimensional probabilistic vectors (i.e., the Hilbert space of dimension
2n is mapped to a probability space of dimension
8n). After this initial mapping, we show how to implement the analogs of single-qubit and two-qubit gates in the probability space using correlation-inducing operations on these classical random variables. The key defining feature of both the mapping to the probability space and the transformations in this space (i.e., operations on the random variables) is that they are not linear, but instead affine. Using this architecture, the evolution of the
2n complex coefficients of the quantum system can be tracked in the joint fully-correlated probabilities of the polynomial number of random variables. We then give specific procedures for implementing (1) the Deutsch-Jozsa algorithm, and (2) the Quantum Fourier Transform in the probability space. Identical to the Quantum case, simulating the Quantum Fourier Transform in the probability space requires
O(n) probabilistic bits and
O(n2) (i.e., quadratic in the number of quantum bits) operations.
The space POVM H(X) of positive operator-valued probability measures on the Borel sets of a compact (or even locally compact) Hausdorff space X with values in B(H), the algebra of linear operators acting on a d-dimensional Hilbert space H, is studied from the perspectives of classical and nonclassical convexity through a transform Γ that associates any positive operator-valued measure ν with a certain completely positive linear map Γ(ν) of the homogeneous C*-algebra C(X)⊗B(H) into B(H). This association is achieved by using an operator-valued integral in which nonclassical random variables (that is, operator-valued functions) are integrated with respect to positive operator-valued measures and which has the feature that the integral of a random quantum effect is itself a quantum effect. A left inverse Ω for Γ yields an integral representation, along the lines of the classical Riesz representation theorem for linear functionals on C(X), of certain (but not all) unital completely positive linear maps φ:C(X)⊗B(H)→B(H). The extremal and C*-extremal points of POVM H(X) are determined.