Bulletin of the American Physical Society
APS March Meeting 2010
Volume 55, Number 2
Monday–Friday, March 15–19, 2010; Portland, Oregon
Session A26: Focus Session: Recent Progress in Quantum Algorithms and Computational Complexity 
Hide Abstracts 
Sponsoring Units: GQI Chair: Dave Bacon, University of Washington Room: D136 
Monday, March 15, 2010 8:00AM  8:36AM 
A26.00001: QIP = PSPACE Invited Speaker: Sarvagya Upadhyay 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). [Preview Abstract] 
Monday, March 15, 2010 8:36AM  8:48AM 
A26.00002: Interacting boson problems can be QMAhard TzuChieh Wei, Michele Mosca, Ashwin Nayak Computing the groundstate 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 socalled 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 QMAhard. In addition, we show that the bosonic version of the socalled Nrepresentability problem is QMAcomplete, as hard as its fermionic version. As a consequence, these problems are unlikely to have efficient quantum algorithms. [Preview Abstract] 
Monday, March 15, 2010 8:48AM  9:00AM 
A26.00003: Towards Quantum Chemistry on a Quantum Computer Benjamin Lanyon, James Whitfield, Geoffrey Gillett, Michael Goggin, Marcelo Almeida, Ivan Kassal, Jacob Biamonte, Masoud Mohseni, Benjamin Powell, Marco Barbieri, Al\'an AspuruGuzik, Andrew White Exact firstprinciples 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 resourcescaling. In this work, we experimentally realize the calculation of molecular properties on a smallscale photonic quantum computerobtaining 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 largescale 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 quantumchemical applications. [Preview Abstract] 
Monday, March 15, 2010 9:00AM  9:12AM 
A26.00004: New directions for quantum lattice gases Peter Love 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. [Preview Abstract] 

A26.00005: ABSTRACT WITHDRAWN 
Monday, March 15, 2010 9:24AM  9:36AM 
A26.00006: First order phase transition in the Quantum Adiabatic Algorithm A. P. Young, S. Knysh, V. N. Smelyanskiy 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. [Preview Abstract] 
Monday, March 15, 2010 9:36AM  9:48AM 
A26.00007: Ground state problem of frustrated spin systems due to quantum annealing using the transverse interaction Yohei Saika, Junichi Inoue 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. [Preview Abstract] 
Monday, March 15, 2010 9:48AM  10:00AM 
A26.00008: Quantum walks in momentum space Michael S. Underwood, David L. Feder 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 walkbased 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 [quantph] (2009) [Preview Abstract] 
Monday, March 15, 2010 10:00AM  10:12AM 
A26.00009: Quantum vs. classical walks with memory two Zlatko Dimcovic, Yevgeniy Kovchegov 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 superexponential 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. [Preview Abstract] 
Monday, March 15, 2010 10:12AM  10:24AM 
A26.00010: Where randomness comes from in the quantum walk? Yutaka Shikano, Kota Chisaki, Etsuo Segawa, Norio Konno While the quantization of the wellknown 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. [Preview Abstract] 
Monday, March 15, 2010 10:24AM  10:36AM 
A26.00011: Using the DeutschJozsa algorithm to partition arrays Samir Lipovaca Using the DeutschJozsa 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 DeutschJozsa 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 DeutschJozsa 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. [Preview Abstract] 
Monday, March 15, 2010 10:36AM  10:48AM 
A26.00012: Performance evaluation of a classical database search that internally simulates an ensemble quantum database search Akira SaiToh Average computation time of classical database search for nontrivial 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 matrixproductstate (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 nontrivial conjunctive and disjunctive normal forms. [Preview Abstract] 
Follow Us 
Engage
Become an APS Member 
My APS
Renew Membership 
Information for 
About APSThe American Physical Society (APS) is a nonprofit membership organization working to advance the knowledge of physics. 
© 2020 American Physical Society
 All rights reserved  Terms of Use
 Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 207403844
(301) 2093200
Editorial Office
1 Research Road, Ridge, NY 119612701
(631) 5914000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 200452001
(202) 6628700