Bulletin of the American Physical Society
APS March Meeting 2021
Volume 66, Number 1
Monday–Friday, March 15–19, 2021; Virtual; Time Zone: Central Daylight Time, USA
Session R34: Quantum Computing Algorithms IIFocus Live
|
Hide Abstracts |
Sponsoring Units: DQI Chair: Amara Katabarwa, Zapata Computing Inc |
Thursday, March 18, 2021 8:00AM - 8:12AM Live |
R34.00001: A Quantum Algorithm for String Matching Pradeep Niroula, Yunseong Nam Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N. Our algorithm has a time complexity of O(√N ) and a modest space complexity of O(N + M ). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes. |
Thursday, March 18, 2021 8:12AM - 8:24AM Live |
R34.00002: Reducing the classical complexity of boson sampling via algebraic graph theory Owen Doty An active area of current quantum information research is identifying tasks that intermediate-size quantum systems can potentially perform more efficiently than classical computers, such as the simulation of quantum many body systems. One such task is boson sampling, the determination of the output probabilities for photons (non-interacting bosons) scattered by the linear elements of an optical apparatus, such as beam splitters and phase shifters. Classically, this calculation is dominated by the determination of a matrix permanent, which scales exponentially with the number of bosons. The permanent can be expressed as the determinant of the adjacency matrix of a weighted hypercube graph, which doesn’t seem to be much help. However, unweighted hypercube graphs can be reduced via equitable vertex partitioning to weighted path graphs, whose determinants are exponentially more efficient to compute. In this work, we make use of these ideas in algebraic graph theory to explore the intriguing possibility that boson sampling probabilities could be efficiently computed classically for a subset of possible optical elements. |
Thursday, March 18, 2021 8:24AM - 8:36AM Live |
R34.00003: Quantum Hypothesis Testing for Non-Abelian Representations Zane Rossi, Isaac Chuang How can prior knowledge of the query set be leveraged to construct efficient protocols for hypothesis testing among quantum channels? Specifically this work addresses the problem of distinguishing multiple unitary quantum channels in the serial adaptive query model under the assumption of known, non-trivial algebraic relations between them. This work shows, by explicit construction, that when the query set faithfully represents a finite subgroup of SU(2) the recently developed technique of quantum signal processing can be applied to build efficient algorithms for quantum multiple hypothesis testing. These algorithms intuitively encode information about the query set and are exponentially more efficient in the instance size than naive reductions to binary hypothesis testing. Moreover, this method illustrates a novel technique for transforming questions in quantum inference to those in the well-understood field of functional approximation. We provide generalizations to larger groups, shows robustness to noise, and give indication that, for a rich subset of quantum hypothesis testing, knowledge of the algebraic structure of the query set can be employed to improve algorithmic performance. |
Thursday, March 18, 2021 8:36AM - 8:48AM Live |
R34.00004: Quantum Legendre-Fenchel transform David Sutter, Giacomo Nannicini, Tobias Sutter, Stefan Woerner We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. Given access to a convex function evaluated at N points, the algorithm outputs a quantum-mechanical representation of its corresponding discrete Legendre-Fenchel transform evaluated at K points in the transformed space. For a fixed regular discretizaton of the dual space the expected running time scales as O(κ polylog(N,K)), where κ is the condition number of the function. If the discretization of the dual space is chosen adaptively with K equal to N, the running time reduces to O(polylog(N)). We explain how to extend the presented algorithm to the multivariate setting and prove lower bounds for the query complexity, showing that our quantum algorithm is optimal up to polylogarithmic factors. For certain scenarios, such as computing an expectation value of an efficiently-computable observable associated with a Legendre-Fenchel-transformed convex function, the quantum algorithm provides an exponential speedup compared to any classical algorithm. |
Thursday, March 18, 2021 8:48AM - 9:00AM Live |
R34.00005: Quantum Algorithms for Solving Ordinary Differential Equations Benjamin Zanger, Christian Mendl, Martin Schulz, Martin Schreiber Identifying computational tasks suitable for (future) quantum computers is an active field of research. Here we explore utilizing quantum computers for the purpose of solving differential equations. We consider two approaches: (i) basis encoding and fixed-point arithmetic on a digital quantum computer, and (ii) representing and solving high-order Runge-Kutta methods as optimization problems on quantum annealers. Applied to two-dimensional toy model differential equations, we devise and simulate quantum circuits for realizing (i), and implement and run a 6th order Gauss-Legendre collocation method on a D-Wave 2000Q system, showing good agreement with the reference solution. As promising future scenario, the digital arithmetic method could be employed as ``oracle'' within quantum search algorithms for inverse problems. The quantum annealing approach exhibits the largest potential for high-order implicit integration methods. |
Thursday, March 18, 2021 9:00AM - 9:12AM Live |
R34.00006: Solving Black Scholes PDE with a quantum computer Javier Gonzalez Conde, Angel Rodriguez-Rozas, Enrique Solano, Mikel Sanz A fundamental task of quantitative finance is calculating the fair price for options, derivative contracts that give the holder the right to buy or sell an underlying asset on a specified date and strike price. The first successful approach to this problem was Black-Scholes model [1]. Although an analytical solution exists, numerical methods are extensively analyzed to solve this model, serving as the ground for more complex models. It has been tackled stochastically employing a quantum Monte Carlo method with quadratic speedup [2] implemented in the IBM computers [3] and also using an unary representation of the asset value [4]. |
Thursday, March 18, 2021 9:12AM - 9:24AM Live |
R34.00007: Quantum Computing for Constraint Programming Kyle Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, Eleanor G Rieffel Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions, and solved with backtracking tree search interleaved with logical inference. Motivated by recent advances in gate-model quantum computers and quantum algorithms, we investigate the application of quantum computing to CP. We introduce a quantum-accelerated filtering algorithm for the AllDifferent global constraint, leveraging quantum algorithms for graph problems, and demonstrate its applicability in accelerating other global constraints with a similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, providing preliminary resource estimates and a discussion of the tradeoffs therein. We conclude that CP is a promising candidate application for early fault-tolerant quantum computers. |
Thursday, March 18, 2021 9:24AM - 9:36AM Live |
R34.00008: Space-efficient binary optimization for variational quantum computing Zoltan Zimboras, Adam Glos, Aleksandra Krawiec In the era of Noisy Intermediate-Scale Quantum (NISQ) computers it is crucial to design quantum algorithms which do not require many qubits or deep circuits. Unfortunately, the most well-known quantum algorithms are too demanding to be run on currently available quantum devices. Moreover, even the state-of-the-art algorithms developed for the NISQ era often suffer from high space complexity requirements for particular problem classes. In this paper, we show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem (TSP), a paradigmatic optimization task, at the cost of having deeper variational circuits. While the focus is on this particular problem, we claim that the approach can be generalized for other problems where the standard bit-encoding is highly inefficient. Finally, we also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models. All the proposed encodings remain efficient to implement within the Quantum Approximate Optimization Algorithm framework. |
Thursday, March 18, 2021 9:36AM - 9:48AM Live |
R34.00009: Low Overhead Universality Using Z Gates in a Uniform Constant X Field on a 1D Chain Brian Barch, Razieh Mohseninia, Paolo Zanardi, Daniel Lidar We show that the method of quantum computation defined by applying Z-diagonal Hamiltonians in the presence of a uniform and constant external X field (as motivated, e.g., by quantum annealing using flux qubits) achieves universal quantum computation. Universality is demonstrated by construction of a universal gate set with O(1) depth overhead, and holds even if the Hamiltonian is restricted to nearest neighbor interactions on a 1D chain. We then use this construction to describe a circuit whose output distribution cannot be classically simulated unless the polynomial hierarchy collapses, with the goal of providing a potential method of demonstrating quantum supremacy. Our model can achieve quantum supremacy in O(n) depth, equivalent to the circuit model despite a higher degree of homogeneity. |
Thursday, March 18, 2021 9:48AM - 10:00AM Live |
R34.00010: Iterative Optimizations to Quantum Phase Estimation and Related Algorithms Scott Johnstun, Jean-Francois S Van Huele The quantum phase estimation algorithm (QPEA) is of fundamental importance in quantum computation. It can be used to perform digital simulation of quantum Hamiltonians on quantum information processors. We study the different optimizations of the QPEA, including circular statistics and iterative optimization, compared to the default majority rule algorithm by comparing their performance when simulating Heisenberg-type Hamiltonians in quantum simulations and in experiments on IBM quantum computers. We investigate to what extent the clear improvement the technique of iterative optimization of the algorithm shows for the Heisenberg-type dynamics can be reproduced for other quantum algorithms. We present results for both simulations and actual implementation on IBM quantum computers. |
Thursday, March 18, 2021 10:00AM - 10:36AM Not Participating |
R34.00011: Symmetries, Graph Properties, and Quantum Speedups Invited Speaker: Shalev Ben-David Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? |
Thursday, March 18, 2021 10:36AM - 10:48AM Live |
R34.00012: Quantum state verification in the quantum linear systems problem Rolando Somma, Yigit Subasi We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form Ax=b. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires q=Ω(κ) uses of a unitary that prepares a quantum state proportional to b, and its inverse in the worst case. Here, κ is the condition number of the matrix A. For typical instances, we show that q=Ω(sqrt(κ)) with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. The lower bounds for prepare-and-measure verification protocols are quadratically worse. An implication of our results is that variational and related approaches to this problem are significantly less efficient than other known approaches, which are guaranteed to converge. |
Thursday, March 18, 2021 10:48AM - 11:00AM On Demand |
R34.00013: Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization Yuval Sanders, Dominic Berry, Pedro Costa, Louis Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, Ryan Babbush Here we explore which heuristic-based quantum algorithms for combinatorial optimization are practical on a small fault-tolerant quantum computer. We compile circuits for the bottleneck step of several heuristic approaches to combinatorial optimization and report for how long and for what size systems one can perform these heuristics in a superconducting quantum processor protected from error by the surface code. Our results discourage the notion that any quantum optimization heuristic realizing only a quadratic speedup will achieve an advantage over classical algorithms on modest superconducting qubit surface code processors without significant improvements in the implementation of the surface code. For instance, under quantum-favorable assumptions, our analysis suggests that quantum accelerated simulated annealing would require roughly a day and a million physical qubits to optimize spin glasses that could be solved by classical simulated annealing in about four CPU-minutes. |
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