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.
We start with the simplest quantum system (a two-level system, i.e., a qubit) and discuss a one-to-one mapping of the quantum state in a two-dimensional Hilbert space to a vector in an eight dimensional probability space (probability simplex). We then show how the usual transformations of the quantum state, specifically the Hadamard gate and the single-qubit phase gate, can be accomplished with appropriate transformations of the mapped vector in the probability simplex. One key defining feature of both the mapping to the simplex and the transformations in the simplex is that they are not linear. These results show that both the initial state and the time evolution of a qubit can be fully captured in an eight dimensional probability simplex (or equivalently using three classical probabilistic bits). We then discuss multi-partite quantum systems and their mapping to the probability simplex. Here, the key tool is the identical tensor product structure of combining multiple quantum systems as well as multiple probability spaces. Specifically, we explicitly show how to implement an analog of the two-qubit controlled-not (CNOT) gate in the simplex. We leave it an open problem how much the quantum dynamics of
N qubits can be captured in a probability simplex with
3N classical probabilistic bits. Finally, we also discuss the equivalent of the Schrodinger's equation for the wavefunction (in a Hilbert space of arbitrary dimension), which dictates the time evolution of the vectors in the simplex.
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.
Review of probability representation of quantum mechanics where the system states are identified with fair probability distributions is presented. Examples of qubits and qutrits are given in detail. The explicit expressions of the qubit density matrices and qubit state vectors in terms of probabilities of dichotomic random variables are discussed. The wave function of a qubit state, and its phase which is not contained in the density matrix of the state, are expressed in terms of the dichotomic probabilities. The generalisation of the probability representation to the case of qudit state is considered. The Schrödinger–like equation for spectra of Hermitian and non Hermitian Hamiltonians is written in the new form of equation for the dichotomic probabilities.
In the Bloch sphere picture, one finds the coefficients for expanding a single-qubit density operator in terms of the identity and Pauli matrices. A generalization to
n qubits via tensor products represents a density operator by a real vector of length
4n, conceptually similar to a state vector. Here, we study this approach for the purpose of quantum circuit simulation, including noise processes. The tensor structure leads to computationally efficient algorithms for applying circuit gates and performing few-qubit quantum operations. In view of variational circuit optimization, we study ``backpropagation'' through a quantum circuit and gradient computation based on this representation, and generalize our analysis to the Lindblad equation for modeling the (nonunitary) time evolution of a density operator.
The conventional paradigm of quantum computing is discrete: It utilizes discrete sets of gates to realize bitstring-to-bitstring mappings, some of them arguably intractable for classical computers. In parametrized quantum approaches, the input becomes continuous and the output represents real-valued functions. While the universality of discrete quantum computers is well understood, basic questions remained open in the continuous case. We focus on universality of multivariate functions. Current approaches require either a number of qubits scaling linearly with the dimension of the input for fixed encodings or a tunable encoding procedure in single-qubit circuits. The question of whether universality can be reached with a fixed encoding and sublinearly many qubits remained open for the last five years. In this paper, we answer this question in the affirmative for arbitrary multivariate functions. We provide two methods: (1) a single-qubit circuit where each coordinate of the arguments to the function to represent is input independently and (2) a multiqubit approach where all coordinates are input in one step, with number of qubits scaling logarithmically with the dimension of the argument of the function of interest. We view the first result of inherent and fundamental interest, whereas the second result opens the path toward representing functions whose arguments are densely encoded in a unitary operation, possibly encoding, for instance, quantum processes.