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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Quantum algorithms for solving the Quantum Linear System (QLS) problem areamong the most investigated quantum algorithms of recent times, with potentialapplications including the solution of computationally intractable differentialequations and speed-ups in machine learning. A fundamental parameter governingthe efficiency of QLS solvers is $\kappa$, the condition number of thecoefficient matrix $A$, as it has been known since the inception of the QLSproblem that for worst-case instances the runtime scales at least linearly in$\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for thecase of positive-definite matrices classical algorithms can solve linearsystems with a runtime scaling as $\sqrt{\kappa}$, a quadratic improvementcompared to the the indefinite case. It is then natural to ask whether QLSsolvers may hold an analogous improvement. In this work we answer the questionin the negative, showing that solving a QLS entails a runtime linear in$\kappa$ also when $A$ is positive definite. We then identify broad classes ofpositive-definite QLS where this lower bound can be circumvented and presenttwo new quantum algorithms featuring a quadratic speed-up in $\kappa$: thefirst is based on efficiently implementing a matrix-block-encoding of $A^{-1}$,the second constructs a decomposition of the form $A = L L^\dagger$ toprecondition the system. These methods are widely applicable and both allow toefficiently solve BQP-complete problems.

On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number