Session A26: Focus Session: Recent Progress in Quantum Algorithms and Computational Complexity

QIP = PSPACE

Efficient proof verification is a fundamental notion in theoretical computer science, where an all powerful prover tries to convince a verifier that a proof of a certain hypothesis is correct. The prover can do anything but the verifier can only run an efficient procedure (called the verification process) such that if the proof is correct, then the verifier always accepts and if the proof is incorrect, then the verifier accepts with very small probability. The interactive proof system is one of the several models of computation based on the notions of proof verification where a resource bounded verifier interacts with an all powerful prover with the objective of verifying whether a purported proof is correct or not. It is known that the class of computational problems having an interactive proof system (denoted $\mathsf{IP}$) is precisely the class of problems that can be solved using polynomial space on a classical computer (denoted $\mathsf{PSPACE}$). In other words, \[ \mathsf{IP} = \mathsf{PSPACE}. \] The quanutm variant of interactive proof systems is defined similarly except that the prover and the verifier are allowed to exchange and process quantum information. For the past decade, it was known that the class of computational problems that admit a quantum interactive proof system (denoted $\mathsf{QIP}$) contains the class of problems in $\mathsf{IP}$. In computer science terms, $\mathsf{IP} = \mathsf{PSPACE} \subseteq \mathsf{QIP}$. In this talk, I will show that the other containment also holds. That is, any computational problem that admits a quantum interactive proof system also admits a classical interactive proof system. This establishes that efficient quantum verification is equivalent to efficient classical verification and hence providing an alternate characterization of $\mathsf{PSPACE}$ from the quantum information perspective: \[ \mathsf{QIP} = \mathsf{PSPACE}. \] This is a joint work with Rahul Jain (National University of Singapore), Zhengfeng Ji (Perimeter Institute for Theoretical Physics), and John Watrous (University of Waterloo).   

Interacting boson problems can be QMA-hard

Computing the ground-state energy of interacting electron (fermion) problems has recently been shown to be hard for QMA, a quantum analogue of the complexity class NP. Fermionic problems are usually hard, a phenomenon widely attributed to the so-called sign problem occurring in Quantum Monte Carlo simulations. The corresponding bosonic problems are, according to conventional wisdom, tractable. Here, we discuss the complexity of interacting boson problems and show that they can also be QMA-hard. In addition, we show that the bosonic version of the so-called N-representability problem is QMA-complete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms.   

Towards Quantum Chemistry on a Quantum Computer

Exact first-principles calculations of molecular properties are currently intractable because the number of conventional computational resources required grow exponentially with molecular size. A solution is to build a quantum computer, which would suffer only a polynomial resource-scaling. In this work, we experimentally realize the calculation of molecular properties on a small-scale photonic quantum computer|obtaining the complete energy spectrum of the hydrogen molecule (H2) in a minimal basis, to 20 bits of precision. We detail how the technique can be expanded to solve large-scale chemical problems that lie beyond the reach of modern supercomputers. Our results represent an early practical step toward a powerful tool for a broad range of quantum-chemical applications.   

New directions for quantum lattice gases

Quantum Lattice Gas Automata are an extension of classical Lattice Gas Automata with the added constraints of linearity and unitary evolution. They were defined in the late 1990s by Meyer, and Boghosian and Taylor. We present a unified version of these models and study them from the point of view of the quantum simulation of problems of quantum dynamics of practical interest including chemical reactive scattering.   

First order phase transition in the Quantum Adiabatic Algorithm

We investigate the complexity of the Quantum Adiabatic Algorithm using quantum Monte Carlo simulations incorporating parallel tempering for sizes up to $N = 256$. For a particular model, known as Exact Cover, we find that an increasing fraction of instances have a first order (discontinuous) quantum phase transition during the evolution of the algorithm. This implies a very small gap (probably exponential) and hence a very long running time for the algorithm to succeed. Preliminary results on other models will also be reported.   

Ground state problem of frustrated spin systems due to quantum annealing using the transverse interaction

We investigate the performance of quantum annealing (QA)/quantum adiabatic evolution (QAE) using the transverse interaction for the ground state problem of frustrated spin systems. As a first example, by solving the Schrodinger equation for a small size system which has the degenerate ground states of the target system, we find that the QA/QAE selectively obtain the optimal solution among the degenerate classical ground states, if we assume the kinetic energy appropriately. Then, we also investigate the ground states of the quantum annealing system composed of the frustrated spin system whose ground state has the macroscopic degeneracy in the thermodynamic limit. The spin wave approximation finds that one ordered state becomes stable among the degeneracy in the ground states of the target system, if we introduce the appropriate kinetic energy term into the quantum annealing system, such as the transverse interaction. These results suggest that the QA/QAE can selectively obtain the ground state if we assume appropriate models of the kinetic energy term.   

Quantum walks in momentum space

It has recently been shown that universal quantum computation can be achieved via quantum walks, both continuous [1] and discrete [2]. In analogy to the standard circuit model for quantum algorithms, these quantum walk-based proposals require a `rail' for each computational basis state, meaning that the number of these rails must grow exponentially with the number of qubits. The quantum walker travels from left to right along the rails, and gates are enacted via additions to the rails or connections among them. While these methods employ large numbers of spatial states for even simple gates on small numbers of qubits, they only require a small number of momentum eigenstates. With this in mind, we explore the promise of performing quantum walks in momentum space to drastically reduce the number of required resources. \\[4pt] [1] Childs. Phys.\ Rev.\ Lett.\ \textbf{102} 180501 (2009) \\[0pt] [2] Lovett et al. arXiv:0910.1024v2 [quant-ph] (2009)   

Quantum vs. classical walks with memory two

Quantum walks is an emerging field in quantum computing. It is expected to become the next most effective tool in speeding up quantum algorithms, possibly achieving the similar gain in speed as was the case with Gibbs sampling in classical computing. There already exist examples of super-exponential speed up using only quantum walks. Markov chains, or random walks on graphs, have many uses in physics; and walks with memory are standard models for a number of phenomena. We study persistent quantum walks, and compare them with equivalent classical Markov processes. The first question to ask is how the mixing time compares between persistent quantum and classical walks. Since quantum walks are generated by unitary matrices, they do not converge to a stationary state. The mixing time is then naturally introduced via a limiting distribution defined as the average of the probability distributions over time (Cesaro sum). We compare the mixing times, along with other properties, using numerical methods and spectral analysis. Our preliminary results indicate a significant speedup in some cases, and a number of other interesting aspects of quantum walks.   

Where randomness comes from in the quantum walk?

While the quantization of the well-known random walk is called a quantum ``random'' walk, one has not yet shown the origin and qualification of randomness. To construct an indicator of randomness, we consider the quantum walk with the periodic position measurement. We analytically show the limit distribution of this simple model, which is the obtained distribution as the convergence as the distribution under the proper time scale, to explain the origin and qualification of randomness in the quantum walk. In the presentation, the interpretation of our mathematical result will be focused on.   

Using the Deutsch-Jozsa algorithm to partition arrays

Using the Deutsch-Jozsa algorithm, we will develop a method for solving a class of problems in which we need to determine parts of an array and then apply a specified function to each independent part. Since present quantum computers are not robust enough for code writing and execution, we will build a model of a vector quantum computer that implements the Deutsch-Jozsa algorithm from a machine language view using the APL2 programming language. The core of the method is an operator (DJBOX) which allows evaluation of an arbitrary function f by the Deutsch-Jozsa algorithm. Two key functions of the method are GET{\_}PARTITION and CALC{\_}WITH{\_}PARTITIONS. The GET{\_}PARTITION function determines parts of an array based on the function f. The CALC{\_}WITH{\_}PARTITIONS function determines parts of an array based on the function f and then applies another function to each independent part. We will imagine the method is implemented on the above vector quantum computer. We will show that the method can be successfully executed.   

Performance evaluation of a classical database search that internally simulates an ensemble quantum database search

Average computation time of classical database search for non-trivial oracles, such as one for SAT, is known to exhibit a certain dependence on the constraint density of instances. We investigate this property for a solver that internally uses a matrix-product-state (MPS) simulation of an extended Bruschweiler search. The database search tool that we had used in [A. SaiToh and M. Kitagawa, Phys. Rev. A 73, 062332 (2006)] has been extended in precision and improved in the speed. This enabled us to evaluate the tool for a larger size of inputs. It is found that the dependence on the constraint density for our tool is different from those for the conventional solvers; this suggests that the MPS approach is useful as a complementary method. Results are shown for several non-trivial conjunctive and disjunctive normal forms.