English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a quantum interior point method (IPM) for semi-definite programs that has a worst-case running time of Õ(n2.5 / ξ2 μ κ 3 log(1/ε)). The algorithm outputs a pair of matrices (S,Y) that have objective value within ε of the optimal and satisfy the constraints approximately to error xi. The parameter mu is at most √2n while kappa is an upper bound on the condition number of the intermediate solution matrices arising in the classical IPM. For the case where κ ≪ n5/6, our method provides a significant polynomial speedup over the best-known classical semi-definite program solvers that have a worst-case running time of Õ(n6). For linear programs, our algorithm has a running time of Õ(n1.5 / ξ2 μ κ 3 log (1/ε)) with the same guarantees and with parameter μ < √2n. Our technical contributions include an efficient quantum procedure for solving the Newton linear systems arising in the classical IPMs, an efficient pure state tomography algorithm, and an analysis of the IPM where the linear systems are solved approximately. Our results pave the way for the development of quantum algorithms with significant polynomial speedups for applications in optimization and machine learning.

A Quantum Interior Point Method for LPs and SDPs