{"id":189,"date":"2023-06-13T07:19:46","date_gmt":"2023-06-13T07:19:46","guid":{"rendered":"https:\/\/www.ccor.hu\/?p=189"},"modified":"2023-06-13T07:24:57","modified_gmt":"2023-06-13T07:24:57","slug":"ccor-workshop-on-interior-point-algorithm-and-quantum-computing","status":"publish","type":"post","link":"http:\/\/www.ccor.hu\/?p=189","title":{"rendered":"CCOR Workshop on Interior Point Algorithm and Quantum Computing"},"content":{"rendered":"\n

Professor\u00a0Tam\u00e1s Terlaky<\/strong>\u00a0(George N. and Soteria Kledaras ’87 Endowed Chair Professor,\u00a0Quantum Computing Optimization Laboratory,\u00a0Department 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\u00a0Workshop\u00a0on\u00a0Interior Point Algorithm and Quantum Computing<\/em>\u00a0will be organized.<\/p>\n\n\n\n

Venue:<\/strong>\u00a0Corvinus University, Building C, Room: C.714
Date:<\/strong>\u00a0June 15 Thursday, 10.30-14.30\u00a0\u00a0<\/p>\n\n\n\n

Keynote speaker:<\/strong>\u00a0Tam\u00e1s Terlaky (Lehigh University, Bethlehem, PA, USA)
Speakers<\/strong>: Andr\u00e1s Gily\u00e9n (Alfr\u00e9d R\u00e9nyi Institute of Mathematics)
\u2002\u2002\u2002\u2002\u2002\u2002\u00a0 \u00a0 \u00a0Roland T\u00f6r\u00f6k (Corvinus University of Budapest)
\u2002\u2002\u2002\u2002\u2002\u2002\u2002\u2002\u00a0Anita Varga (Budapest University of Technology and Economics)<\/p>\n\n\n\n

Program:<\/strong>
\u00a010.30-11.00:\u00a0Anita Varga: An Ai-Zhang type interior-point framework for linear optimization and a related function class
\u00a011.00-11.30:\u00a0Roland T\u00f6r\u00f6k: Implementation of interior-point algorithms based on different AET functions
\u00a011.30-12.30: Lunch break
\u00a012.30-13.00: Andr\u00e1s Gily\u00e9n: Unbiased quantum gradient computation and its application to quantum tomography
\u00a013.00-14.00:\u00a0Tam\u00e1s Terlaky: New Developments on Quantum Interior Point Methods for LO and SDO
14.00-14.30: Discussion\u00a0<\/p>\n\n\n\n

—————————————————————————————————————-<\/p>\n\n\n\n

Abstracts<\/strong><\/p>\n\n\n\n

Tam\u00e1s Terlaky: New Developments on Quantum Interior Point Methods for LO and SDO<\/em><\/strong><\/p>\n\n\n\n

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 \u201cquantum inspired\u2018\u2019 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\u2019s efficiency using IBMs QISKIT environment.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Andr\u00e1s Gily\u00e9n:  Unbiased quantum gradient computation and its application to quantum tomography<\/em><\/strong><\/p>\n\n\n\n

We describe an unbiased and symmetric version of quantum phase\u00a0estimation, where the probability distribution of the estimates is\u00a0centered around the true value, which then enables\u00a0 us to efficiently\u00a0compute estimates of gradients in an unbiased fashion. We then apply\u00a0these techniques to obtain an approximate classical description of a\u00a0d-dimensional quantum state when given access to a unitary (and its\u00a0inverse) that prepares it. For pure states we characterize the query\u00a0complexity for \u2113_q-norm error up to logarithmic factors. As a special\u00a0case, we show that it takes \u0398(d\/\u03b5) applications of the unitaries to\u00a0obtain an \u03b5-\u2113_2-approximation of the state. For mixed states we consider\u00a0a similar model, where the unitary prepares a purification of the state.\u00a0
In this model we give an efficient algorithm for obtaining Schatten\u00a0q-norm estimates of a rank-r mixed state, giving query upper bounds that\u00a0are close to optimal. In particular, we show that a trace-norm (q=1)\u00a0estimate can be obtained with O(dr\/\u03b5) queries. This improves (assuming\u00a0\u00a0our stronger input model) the \u03b5-dependence over the algorithm of Haah et\u00a0al. (2017) that uses a joint measurement on O(dr\/\u03b52) copies of the\u00a0state.
Joint work with: Joran van Apeldoorn, Arjan Cornelissen, and Giacomo\u00a0Nannicini.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Roland T\u00f6r\u00f6k: Implementation of interior-point algorithms based on different AET functions<\/em><\/strong><\/p>\n\n\n\n

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\u00a0Tibor Ill\u00e9s and Petra Ren\u00e1ta Rig\u00f3.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Anita Varga: An Ai-Zhang type interior-point framework for linear optimization and a related function class<\/em><\/strong><\/p>\n\n\n\n

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.<\/p>\n","protected":false},"excerpt":{"rendered":"

Professor Tam\u00e1s 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. Continue Reading …<\/a><\/span><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-189","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=189"}],"version-history":[{"count":2,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/189\/revisions"}],"predecessor-version":[{"id":195,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=\/wp\/v2\/posts\/189\/revisions\/195"}],"wp:attachment":[{"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=189"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.ccor.hu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}