Bulletin of the American Physical Society
APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016; Baltimore, Maryland
Session H44: Quantum Algorithms |
Hide Abstracts |
Sponsoring Units: GQI Chair: Kenneth Rudinger, Sandia National Labs Room: 347 |
Tuesday, March 15, 2016 2:30PM - 2:42PM |
H44.00001: Quantum linear systems algorithm with exponentially improved dependence on precision Rolando Somma, Andrew Childs, Robin Kothari Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \times N$ matrix $A$ and $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x}=\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time polynomial in $\log N$ and $1/\epsilon$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive. [Preview Abstract] |
(Author Not Attending)
|
H44.00002: QUANTUM ALGORITHM FOR LINEAR PROGRAMMING PROBLEMS Pramod Joag, Dhananjay Mehendale The quantum algorithm (PRL 103, 150502, 2009) solves a system of linear equations with exponential speedup over existing classical algorithms. We show that the above algorithm can be readily adopted in the iterative algorithms for solving linear programming (LP) problems. The first iterative algorithm that we suggest for LP problem follows from duality theory. It consists of finding nonnegative solution of the equation forduality condition; forconstraints imposed by the given primal problem and for constraints imposed by its corresponding dual problem. This problem is called the problem of nonnegative least squares, or simply the NNLS problem. We use a well known method for solving the problem of NNLS due to Lawson and Hanson. This algorithm essentially consists of solving in each iterative step a new system of linear equations . The other iterative algorithms that can be used are those based on interior point methods. The same technique can be adopted for solving network flow problems as these problems can be readily formulated as LP problems. The suggested quantum algorithm cansolveLP problems and Network Flow problems of very large size involving millions of variables. [Preview Abstract] |
Tuesday, March 15, 2016 2:54PM - 3:06PM |
H44.00003: A quantum Algorithm for the Moebius Function Peter Love We give an efficient quantum algorithm for the Moebius function from the natural numbers to {-1,0,1}. The cost of the algorithm is asymptotically quadratic in log n and does not require the computation of the prime factorization of n as an intermediate step. [Preview Abstract] |
Tuesday, March 15, 2016 3:06PM - 3:18PM |
H44.00004: The Deutch-Jozsa algorithm as a suitable framework for MapReduce in a quantum computer Samir Lipovaca The essence of the MapReduce paradigm [1] is a parallel, distributed algorithm across hundreds or thousands machines. In crude fashion this parallelism reminds us of the method of computation by quantum parallelism which is possible only with quantum computers. Deutsch and Jozsa [2] showed that there is a class of problems which can be solved more efficiently by quantum computer than by any classical or stochastic method. The method of computation by quantum parallelism solves the problem with certainty in exponentially less time than any classical computation. This leads to question would it be possible to implement the MapReduce paradigm in a quantum computer and harness this incredible speedup over the classical computation performed by the current computers. Although present quantum computers are not robust enough for code writing and execution, it is worth to explore this question from a theoretical point of view. We will show from a theoretical point of view that the Deutsch-Jozsa algorithm is a suitable framework to implement the MapReduce paradigm in a quantum computer. References: [1] Chuck Lam, \textit{Hadoop in Action}, (Manning Publications Co. Greenwich, CT, USA \copyright 2010). [2] Deutsch, D., Jozsa, R. 1992 \textit{Proc. R. Soc. Lond.} A 439, 553-558. [Preview Abstract] |
Tuesday, March 15, 2016 3:18PM - 3:30PM |
H44.00005: Optimizing Qubit Resources for Quantum Chemistry Simulations in Second Quantization on a Quantum Computer Nikolaj Moll, Andreas Fuhrer, Peter Staar, Ivano Tavernelli Quantum chemistry simulations on a quantum computer suffer from the overhead needed for encoding the fermionic problem in a bosonic system of qubits. By exploiting the block diagonality of a fermionic Hamiltonian, we show that the number of required qubits can be reduced by a factor of two or more. There is no need to go into the basis of the Hilbert space for this reduction because all operations can be performed in the operator space. The scheme is conceived as a pre-computational step that would be performed on a classical computer prior to the actual quantum simulation. We apply this scheme to reduce the number of qubits necessary to simulate both the Hamiltonian of the two-site Fermi-Hubbard model and the hydrogen molecule. Both quantum systems can then be simulated with a two-qubit quantum computer. [Preview Abstract] |
Tuesday, March 15, 2016 3:30PM - 3:42PM |
H44.00006: Modelling Quantum Subsystem Dynamics Jason Dominy, Alireza Shabani, Daniel Lidar We describe a general and consistent mathematical model for linear subsystem quantum dynamical maps, developed from a minimal set of postulates, primary among which is a relaxation of the usual, restrictive assumption of uncorrelated initial system-bath states. The resulting space of physically realizable dynamical maps, far from being limited to only completely positive (CP) maps, comprises essentially all $\mathbb{C}$-linear, Hermiticity-preserving, trace-preserving subsystem maps. We will discuss some implications for the standard theory of open quantum systems and the search for necessary and sufficient conditions for complete positivity. See [1], [2] for additional details. [1] Jason M. Dominy, Alireza Shabani, and Daniel A. Lidar. A general framework for complete positivity. \emph{Quantum Inf. Proc.}, 2015. (To appear). URL: {\tt{http://dx.doi.org/10.1007/ s11128-015-1148-0}}. [2] Jason M. Dominy and Daniel A. Lidar. Beyond complete positivity. {\tt{arXiv:1503.05342}}. [Preview Abstract] |
Tuesday, March 15, 2016 3:42PM - 3:54PM |
H44.00007: Hybrid quantum-classical approach to correlated materials Bela Bauer, Dave Wecker, Andrew J. Millis, Matthew B. Hastings, Matthias Troyer Recent improvements in control of quantum systems make it seem feasible to finally build a programmable general-purpose quantum computer within a decade. While it has been shown that such a quantum computer can in principle solve certain small electronic structure problems and idealized model Hamiltonians, the highly relevant problem of directly solving a complex correlated material appears to require a prohibitive amount of resources. Here, we show that by using a hybrid quantum-classical algorithm that incorporates the power of a small quantum computer into a framework of classical embedding algorithms, the electronic structure of complex correlated materials can be efficiently tackled using a quantum computer. In our approach, the quantum computer solves a small effective quantum impurity problem that is self-consistently determined via a feedback loop between the quantum and classical computation. Use of a quantum computer enables much larger and more accurate simulations than with any known classical algorithm, and will allow many open questions in quantum materials to be resolved once a small quantum computer with around one hundred logical qubits becomes available. [Preview Abstract] |
Tuesday, March 15, 2016 3:54PM - 4:06PM |
H44.00008: A method to efficiently simulate the thermodynamic properties of the Fermi-Hubbard model on a quantum computer Pierre-Luc Dallaire-Demers, Frank Wilhelm-Mauch Many phenomena of strongly correlated materials are encapsulated in the Fermi-Hubbard model whose thermodynamic properties can be computed from its grand canonical potential. In general, there is no closed form expression of the grand canonical potential for lattices of more than one spatial dimension, but solutions can be approximated with cluster perturbation theory. To model long-range effects such as order parameters, a powerful method to compute the cluster's Green's function consists in finding its self-energy through a variational principle. This opens the possibility of studying various phase transitions at finite temperature in the Fermi-Hubbard model. However, a classical cluster solver quickly hits an exponential wall in the memory (or computation time) required to store the computation variables. Here it is shown theoretically that that the cluster solver can be mapped to a subroutine on a quantum computer whose quantum memory scales as the number of orbitals in the simulated cluster. A quantum computer with a few tens of qubits could therefore simulate the thermodynamic properties of complex fermionic lattices inaccessible to classical supercomputers. [Preview Abstract] |
Tuesday, March 15, 2016 4:06PM - 4:18PM |
H44.00009: Efficient Simulation of Dissipative Dynamics Kyungjoo Noh, Victor V. Albert, Chao Shen, Liang Jiang Open quantum systems with engineered dissipations may have more than one steady states. These steady states may form a non-trivial decoherence free subspace (DFS) that can store quantum information against major decoherences. Besides unitary operations within DFS, it is also useful to have dissipative/cooling operations within the DFS. We investigate the possibility of using Hamiltonian perturbation to the engineered dissipation to induce an effective dissipative dynamics within the DFS in a controlled manner. The major challenge is to simulate all the Lindblad jump operators in the master equation. By designing the dissipation within the subspace complementary to the DFS, we can simply use the Hamiltonian perturbation to the designed dissipation with a \textit{single} jump operator to produce an effective dissipation with \textit{multiple} Lindblad jump operators. [Preview Abstract] |
Tuesday, March 15, 2016 4:18PM - 4:30PM |
H44.00010: Racing in parallel: Quantum versus Classical Damian S. Steiger, Matthias Troyer In a fair comparison of the performance of a quantum algorithm to a classical one it is important to treat them on equal footing, both regarding resource usage and parallelism. We show how one may otherwise mistakenly attribute speedup due to parallelism as quantum speedup. We apply such an analysis both to analog quantum devices (quantum annealers) and gate model algorithms and give several examples where a careful analysis of parallelism makes a significant difference in the comparison between classical and quantum algorithms. [Preview Abstract] |
Tuesday, March 15, 2016 4:30PM - 4:42PM |
H44.00011: How far can we push quantum variational algorithms without error correction? Ryan Babbush Recent work has shown that parameterized short quantum circuits can generate powerful variational ansatze for ground states of classically intractable fermionic models. This talk will present numerical and experimental evidence that quantum variational algorithms are also robust to certain errors which plague the gate model. As the number of qubits in superconducting devices keeps increasing, their dynamics are becoming prohibitively expensive to simulate classically. Accordingly, our observations should inspire hope that quantum computers could provide useful insight into important problems in the near future. This talk will conclude by discussing future research directions which could elucidate the viability of executing quantum variational algorithms on classically intractable problems without error correction. [Preview Abstract] |
Tuesday, March 15, 2016 4:42PM - 4:54PM |
H44.00012: A Quantum Algorithm for Estimating Hitting Times of Markov Chains Anirban Narayan Chowdhury, Rolando Somma We present a quantum algorithm to estimate the hitting time of a reversible Markov chain faster than classically possible. To this end, we show that the hitting time is given by an expected value of the inverse of a Hermitian matrix. To obtain this expected value, our algorithm combines three important techniques developed in the literature. One such a technique is called spectral gap amplification and we use it to amplify the gap of the Hermitian matrix or reduce its condition number. We then use a new algorithm by Childs, Kothari, and Somma to implement the inverse of a matrix, and finally use methods developed in the context of quantum metrology to reduce the complexity of expected-value estimation for a given precision. [Preview Abstract] |
Tuesday, March 15, 2016 4:54PM - 5:06PM |
H44.00013: Continuous Time Quantum Walks in finite Dimensions Shanshan Li, Stefan Boettcher Continuous time quantum walk (CTQW) provides optimal quadratic speedup for spatial search on complete graphs, hypercubes, and connected random graphs compared to classical algorithms. Instead of these high dimensional graphs, we consider the performance of CTQW on the finite dimensional Migdal-Kadanoff lattices. We relate the critical point for the walk Hamiltonian to the lattice Laplacian. Using renormalization group analysis\footnote{Boettcher, Stefan, and Shanshan Li, Journal of Physics A 48, 415001 (2015)}, we calculate the critical point and derive the search performance on instances of different spectral dimension. For those with integer dimension, we reproduce the known algorithmic efficiency on regular lattices. In particular, we show that on these finite dimensional graphs, the algorithmic efficiency of quantum walk is entirely determined by the spectral dimension of the Laplacian. Quadratic speedup can only be achieved when the spectral dimension is larger than four. [Preview Abstract] |
Tuesday, March 15, 2016 5:06PM - 5:18PM |
H44.00014: Spatial search by quantum walk is optimal for almost all graphs Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, Yasser Omar The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdös-Renyi random graphs, i.e. graphs of $n$ vertices where each edge exists with probability $p$, search by CTQW is almost surely optimal as long as $p\geq \log^{3/2}(n)/n$. Consequently, we show that quantum spatial search is in fact optimal for almost all graphs, meaning that the fraction of graphs of $n$ vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures. [Preview Abstract] |
Tuesday, March 15, 2016 5:18PM - 5:30PM |
H44.00015: Connecting the Discrete-time and Continuous-time Quantum Walks Albert Schmitz Much work has gone into connecting the discrete-time and continuous-time versions of the quantum walk. This talk will demonstrate a method for finding an appropriate coin operator to simulate the continuous-time dynamics generated by a graph Hamiltonian for any arbitrary bigraph. This method draws a connection between a continuous-time model on the standard 1D and 2D lattice and the Hadamard walk. Furthermore, some extensions will be discussed with applications to algorithm design. [Preview Abstract] |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700