Professor Tamás Terlaky (George N. and Soteria Kledaras ’87 Endowed Chair Professor, Quantum Computing Optimization Laboratory, Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA) will be a guest of the Corvinus Center for Operation Research (CCOR). As part of his visit, the CCOR Workshop on Interior Point Algorithm and Quantum Computing will be organized.
Venue: Corvinus University, Building C, Room: C.714
Date: June 15 Thursday, 10.30-14.30
Keynote speaker: Tamás Terlaky (Lehigh University, Bethlehem, PA, USA)
Speakers: András Gilyén (Alfréd Rényi Institute of Mathematics)
Roland Török (Corvinus University of Budapest)
Anita Varga (Budapest University of Technology and Economics)
Program:
10.30-11.00: Anita Varga: An Ai-Zhang type interior-point framework for linear optimization and a related function class
11.00-11.30: Roland Török: Implementation of interior-point algorithms based on different AET functions
11.30-12.30: Lunch break
12.30-13.00: András Gilyén: Unbiased quantum gradient computation and its application to quantum tomography
13.00-14.00: Tamás Terlaky: New Developments on Quantum Interior Point Methods for LO and SDO
14.00-14.30: Discussion
—————————————————————————————————————-
Abstracts
Tamás Terlaky: New Developments on Quantum Interior Point Methods for LO and SDO
Quantum Interior Point Methods (QIPMs) build on classic polynomial time IPMs. With the emergence of quantum computing we apply Quantum Linear System Algorithms (QLSAs) to Newton systems within IPMs to gain quantum speedup in solving Linear Optimization (LO) and Semidefinite Optimization (SDO) problems. Due to their inexact nature, QLSAs mandate the development of inexact variants of IPMs which, due to the inexact nature of their computations, by default are inexact infeasible methods.
We propose “quantum inspired‘’ Inexact-Feasible IPMs (IF-IPM) for LO and SDO problems, using novel Newton systems to generate inexact but feasible steps. We show that IF-QIPMs enjoys the to-date best iteration complexity. Further, we explore how QLSAs can be used efficiently in iterative refinement schemes to find optimal solutions without excessive calls to QLSAs. Finally, we discuss our experiments with the proposed IF-IPM’s efficiency using IBMs QISKIT environment.
András Gilyén: Unbiased quantum gradient computation and its application to quantum tomography
We describe an unbiased and symmetric version of quantum phase estimation, where the probability distribution of the estimates is centered around the true value, which then enables us to efficiently compute estimates of gradients in an unbiased fashion. We then apply these techniques to obtain an approximate classical description of a d-dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure states we characterize the query complexity for ℓ_q-norm error up to logarithmic factors. As a special case, we show that it takes Θ(d/ε) applications of the unitaries to obtain an ε-ℓ_2-approximation of the state. For mixed states we consider a similar model, where the unitary prepares a purification of the state.
In this model we give an efficient algorithm for obtaining Schatten q-norm estimates of a rank-r mixed state, giving query upper bounds that are close to optimal. In particular, we show that a trace-norm (q=1) estimate can be obtained with O(dr/ε) queries. This improves (assuming our stronger input model) the ε-dependence over the algorithm of Haah et al. (2017) that uses a joint measurement on O(dr/ε2) copies of the state.
Joint work with: Joran van Apeldoorn, Arjan Cornelissen, and Giacomo Nannicini.
Roland Török: Implementation of interior-point algorithms based on different AET functions
In this presentation, we plan to show numerical methods used in the implementation of interior point algorithms (IPAs) for solving sufficient linear complementarity problems. For the determination of the search directions we used the algebraically equivalent transformation (AET) of the central path system. We defined a class of AET functions in case of primal-dual (PD) IPAs. We implemented the PD IPAs based on some AET functions belonging to the new class of functions. Furthermore, we show numerical results regarding predictor-corrector (PC) IPAs with the selected AET functions from the above mentioned class. We present our numerical results on a test example set that were generated using a matrix having exponential handicap, called Csizmadia matrix. We also compare our numerical results to methods that use kernel functions for determining search directions.
Joint work with Tibor Illés and Petra Renáta Rigó.
Anita Varga: An Ai-Zhang type interior-point framework for linear optimization and a related function class
Based on their step size, interior point algorithms (IPAs) can be divided into two main groups, short-step and long-step methods. Even though, in general, better theoretical complexity can be achieved for short-step variants, long-step IPAs perform better in practice. The first long-step IPA with the same iteration complexity as short-step variants was introduced by Ai and Zhang in 2005.
To determine new search directions for IPAs, Darvay proposed the algebraically equivalent transformation (AET) technique in 2002. His main idea was to apply an invertible and continuously differentiable function to the centering equation of the central path system.
In our work, we combined these two approaches. The main question we addressed is what type of functions Darvay’s technique can be applied with so that the desired convergence and complexity properties of an Ai-Zhang type algorithm can be proved. For this purpose, we defined a general Ai-Zhang type long-step algorithmic framework, where the transforming function is part of the input. We gave a set of necessary conditions on this function and proved that if these conditions are satisfied, the general algorithm is convergent and has the best known iteration complexity. This way, we defined a new function class related to the AET technique.
Besides discussing the theoretical results, we also present our numerical results to compare the practical performance of the algorithm variants based on different functions.
Joint work with Marianna E.-Nagy.