Bulletin of the American Physical Society
APS March Meeting 2021
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 dataset appear ubiquitously in text and image processing. Here, we present an explicit, circuitlevel implementation of a quantum patternmatching 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 prefaulttolerant and faulttolerant 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 intermediatesize 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 (noninteracting 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 NonAbelian 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, nontrivial 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 wellunderstood 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 LegendreFenchel transform David Sutter, Giacomo Nannicini, Tobias Sutter, Stefan Woerner We present a quantum algorithm to compute the discrete LegendreFenchel transform. Given access to a convex function evaluated at N points, the algorithm outputs a quantummechanical representation of its corresponding discrete LegendreFenchel 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 efficientlycomputable observable associated with a LegendreFencheltransformed convex function, the quantum algorithm provides an exponential speedup compared to any classical algorithm. 
Thursday, March 18, 2021 8:48AM  9:00AM 
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 fixedpoint arithmetic on a digital quantum computer, and (ii) representing and solving highorder RungeKutta methods as optimization problems on quantum annealers. Applied to twodimensional toy model differential equations, we devise and simulate quantum circuits for realizing (i), and implement and run a 6^{th} order GaussLegendre collocation method on a DWave 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 highorder 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 RodriguezRozas, 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 BlackScholes 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 gatemodel quantum computers and quantum algorithms, we investigate the application of quantum computing to CP. We introduce a quantumaccelerated 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 faulttolerant quantum computers. 
Thursday, March 18, 2021 9:24AM  9:36AM Live 
R34.00008: Spaceefficient binary optimization for variational quantum computing Zoltan Zimboras, Adam Glos, Aleksandra Krawiec In the era of Noisy IntermediateScale Quantum (NISQ) computers it is crucial to design quantum algorithms which do not require many qubits or deep circuits. Unfortunately, the most wellknown quantum algorithms are too demanding to be run on currently available quantum devices. Moreover, even the stateoftheart 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 bitencoding is highly inefficient. Finally, we also propose encoding schemes which smoothly interpolate between the qubitefficient and the circuit depthefficient 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 Zdiagonal 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, JeanFrancois 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 Heisenbergtype 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 Heisenbergtype 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 BenDavid 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 prepareandmeasure 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 FaultTolerant 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 heuristicbased quantum algorithms for combinatorial optimization are practical on a small faulttolerant 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 quantumfavorable 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 CPUminutes. 
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. 
© 2021 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