Quantum simulation, which is generically the task to employ quantum computers to simulate quantum physical models, has been one of the most significant motivations of quantum computing. Quantum dynamics, unitary or nonunitary Markovian dynamics driven by local interactions, has been proved to be efficiently simulatable on quantum computers. Extending the underlying models from unitary to nonunitary evolution, and from continuous-time to discrete-time evolution is essential not only for quantum simulation of more general processes, e.g., dissipative processes with evident non-Markovian effects, but also for developing alternative quantum computing models and algorithms. In this thesis, we explore quantum simulation problems mainly from the following three themes. First, we extend quantum simulation framework of Hamiltonian-driven evolution to quantum simulation of quantum channels, combined with the scheme of algorithmic simulation that accepts a promised simulation accuracy, hence algorithmic quantum channel simulation. Our simulation scheme contains a classical preprocessing part, i.e. a classical algorithm for quantum-circuit design, and a quantum part that is the execution of a quantum circuit for the quantum channel simulator. Second, we employ simulation algorithms for arbitrary quantum channels beyond the dilation method. We explore channel decomposition in terms of convex combination of smaller channels, known as generalized extreme channels, which is known as a nontrivial open problem. To attack this problem, we develop an optimization algorithm for approximate decomposition into a convex sum of generalized extreme channels. We provide an ansatz that proves to be able to yield arbitrary generalized extreme channels and allows a precise quantum circuit description. Furthermore, our numerical simulation has demonstrated the validity of our optimization algorithm for low-dimensional quantum channels. Third, by considering quantum simulation problems beyond the rough distinction between digital and analog simulations, and beyond the quantum-state generation problem, we define uniform, strong, and weak quantum simulations from the point view of operator topology. Besides strong simulation of quantum channels, we define a general weak quantum simulation problem, which simulates observable effects instead of the effects on state generation. Also we study the channel simulation problem in the quantum query model, and provide the query complexity by employing uniform quantum simulation method.
Quantum simulation, which is generically the task to employ quantum computers to simulate quantum physical models, has been one of the most significant motivations of quantum computing. Quantum dynamics, unitary or nonunitary Markovian dynamics driven by local interactions, has been proved to be efficiently simulatable on quantum computers. Extending the underlying models from unitary to nonunitary evolution, and from continuous-time to discrete-time evolution is essential not only for quantum simulation of more general processes, e.g., dissipative processes with evident non-Markovian effects, but also for developing alternative quantum computing models and algorithms. In this thesis, we explore quantum simulation problems mainly from the following three themes. First, we extend quantum simulation framework of Hamiltonian-driven evolution to quantum simulation of quantum channels, combined with the scheme of algorithmic simulation that accepts a promised simulation accuracy, hence algorithmic quantum channel simulation. Our simulation scheme contains a classical preprocessing part, i.e. a classical algorithm for quantum-circuit design, and a quantum part that is the execution of a quantum circuit for the quantum channel simulator. Second, we employ simulation algorithms for arbitrary quantum channels beyond the dilation method. We explore channel decomposition in terms of convex combination of smaller channels, known as generalized extreme channels, which is known as a nontrivial open problem. To attack this problem, we develop an optimization algorithm for approximate decomposition into a convex sum of generalized extreme channels. We provide an ansatz that proves to be able to yield arbitrary generalized extreme channels and allows a precise quantum circuit description. Furthermore, our numerical simulation has demonstrated the validity of our optimization algorithm for low-dimensional quantum channels. Third, by considering quantum simulation problems beyond the rough distinction between digital and analog simulations, and beyond the quantum-state generation problem, we define uniform, strong, and weak quantum simulations from the point view of operator topology. Besides strong simulation of quantum channels, we define a general weak quantum simulation problem, which simulates observable effects instead of the effects on state generation. Also we study the channel simulation problem in the quantum query model, and provide the query complexity by employing uniform quantum simulation method.
Abstract Quantum simulation is one of the central discipline to demonstrate the power of quantum computing. In recent years, the theoretical framework of quantum superchannels has been developed and applied widely as the extension of quantum channels. In this work, we study the quantum circuit simulation task of superchannels. We develop a quantum superchannel simulation algorithm based on the convex decomposition into sum of extreme superchannels. We demonstrate the algorithm by numerical simulation of qubit superchannels with high accuracy, making it applicable to current experimental platforms. Our study stands as an expansion of the superchannel theory to the field of quantum simulation and algorithm, as well as an extension of quantum simulation from channels and open-system dynamics to superchannels and processes with manifest quantum memory effects.
Simulating quantum mechanical evolutions in general is difficult on classical computers because the size of the Hilbert space grows exponentially with the number of particles involved in the simulations. However, a quantum computer, which obeys the laws of quantum mechanics, is believed to perform such simulations more efficiently. The time evolution operator, a unitary matrix, of a quantum system acts as a quantum gate changing the state of the system in time. Therefore, any computation on quantum computers can be interpreted as a unitary transformation on quantum state vectors. Generally, quantum gates are sufficiently simple operations so as to avoid difficulty in the physical implementation. The implementation of a general given computation represented by a unitary matrix on quantum computers requires finding an array of elementary quantum gates describing the desired computation. This describes a matrix decomposition problem known as the quantum circuit design problem. In this dissertation, we address the following questions concerning quantum circuit designs: How hard is it to find suitable quantum circuits for a given computation? What are the possible circuit design methods? How do we apply these to simulations of quantum problems, in particular quantum chemistry problems? To answer these questions, we categorize methods for designing quantum circuits as evolutionary algorithms and deterministic methods. We apply our developed group leaders optimization algorithm, an evolutionary algorithm, to find quantum circuits for known quantum algorithms and the simulation of molecular Hamiltonians. Then, we present a deterministic circuit design approach to produce universal circuits, which can be programmable. Moreover, we show how to use these programmable circuit designs within the quantum phase estimation algorithm to find eigenvalues of nonunitary matrices and study resonances in quantum systems. Finally, the quantum phase estimation algorithm is employed to efficiently solve ranking problems: in particular, multiple network alignment is considered to find the similarities between protein-protein interaction networks and molecular networks.
Over the last two decades the field of quantum simulations has experienced incredible \ngrowth, which, coupled with progress in the development of controllable quantum \nplatforms, has recently begun to allow for the realisation of quantum simulations of a \nplethora of quantum phenomena in a variety of controllable quantum platforms. Within \nthe context of these developments, we investigate within this thesis methods for the \nquantum simulation of open quantum systems. \nMore specically, in the first part of the thesis we consider the simulation of Markovian \nopen quantum systems, and begin by leveraging previously constructed universal \nsets of single-qubit Markovian processes, as well as techniques from Hamiltonian simulation, \nfor the construction of an efficient algorithm for the digital quantum simulation \nof arbitrary single-qubit Markovian open quantum systems. The algorithm we provide, \nwhich requires only a single ancillary qubit, scales slightly superlinearly with respect \nto time, which given a recently proven no fast-forwarding theorem for Markovian dynamics, \nis therefore close to optimal. Building on these results, we then proceed to \nexplicitly construct a universal set of Markovian processes for quantum systems of any \ndimension. Specifically, we prove that any Markovian open quantum system, described \nby a one-parameter semigroup of quantum channels, can be simulated through coherent \noperations and sequential simulations of processes from the universal set. Under the assumption \nthat these universal Markovian processes can be efficiently implemented, this \nallows us to propose an efficient algorithm for a wide class of Markovian open quantum \nsystems, while simultaneously providing a tool for combining and exploiting existing \nsimulation methods. \nIn the second part of this thesis we then consider the simulation of many-body non- \nMarkovian open quantum systems. In particular, we develop an algorithmic procedure \nfor the quantum simulation of system propagators which are not completely positive \nmaps, which allows us to provide an explicit algorithm for the digital quantum simulation \nof many-body locally-indivisible non-Markovian open quantum systems described by \ntime-dependent master equations. Finally we construct generalised Suzuki-Lie-Trotter \ntheorems which allow us to analyse the efficiency of our method, which is expected to \nbe experimentally achievable for a variety of interesting cases.
Quantum channels describe general transformations of the state of a physical system and play a fundamental role in many fields. It promises wide range of applications, because any physical process can be represented as a quantum channel transforming an initial state into a final state. The evolution of system undergoing a quantum channel is not necessary unitary which makes it unrealisable without ancillary system. Inspired by the method performing non-unitary operator by the linear combination of unitary operations, we proposed a quantum algorithm for the simulation of universal single-qubit channel, described by a convex combination of two generalized extreme channels corresponding to four Kraus operators, and is scalable to arbitrary higher dimension. We demonstrate the whole algorithm experimentally using the universal IBM cloud quantum computer and study properties of different qubit quantum channels. We illustrate the quantum capacity of the general qubit quantum channels, which quantifies the amount of quantum information that can be protected. There is a general agreement between the theoretical predictions and the experiments, which strongly supported our method. By realizing arbitrary qubit channel, this work provides a universal way to explore various properties of quantum channel and novel prospect of quantum communication.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
Quantum algorithms hold the promise of fundamentally changing the way we approach problems in physics, chemistry, computer science, and engineering. This thesis explores new provably efficient quantum algorithms for three fundamental directions in quantum computing: simulation, optimization, and estimation. Together, our results in each of these directions contribute to the broader effort of making quantum computation a practical tool for science and engineering. First, in the area of quantum simulation, we propose Wave Matrix Lindbladization, a set of algorithms that extend the philosophy of density matrix exponentiation to Lindbladian dynamics by working with program-state encodings of Lindblad operators. Specifically, when these operators are local, we show that these algorithms are provably efficient by analyzing their sample and gate complexities. Second, for optimization, we study quantum Boltzmann machines as a variational ansatz for ground-state energy estimation, proving efficient gradient estimation and convergence to approximate stationary points. We also propose hybrid quantum-classical algorithms for semidefinite programming, establish rigorous convergence guarantees, and validate their robustness to noise through numerical simulations for applications such as MaxCut. Finally, for estimation, we develop the tapered quantum phase estimation algorithm, a coherent phase estimation method that leverages taper/window functions from signal processing to reach optimal query complexity without relying on expensive coherent median techniques, and we provide error guarantees in both asymptotic and non-asymptotic regimes along with efficient taper state preparation.