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

We analyze the complexity of quantum state verification in the context ofsolving systems of linear equations of the form $A \vec x = \vec b$. We showthat any quantum operation that verifies whether a given quantum state iswithin a constant distance from the solution of the quantum linear systemsproblem requires $q=\Omega(\kappa)$ uses of a unitary that prepares a quantumstate $\left| b \right>$, proportional to $\vec b$, and its inverse in theworst case. Here, $\kappa$ is the condition number of the matrix $A$. Fortypical instances, we show that $q=\Omega(\sqrt \kappa)$ with high probability.These lower bounds are almost achieved if quantum state verification isperformed using known quantum algorithms for the quantum linear systemsproblem. We also analyze the number of copies of $\left| b \right>$ required byverification procedures of the prepare and measure type. In this case, thelower bounds are quadratically worse, being $\Omega(\kappa^2)$ in the worstcase and $\Omega(\kappa)$ in typical instances with high probability. Wediscuss the implications of our results to known variational and relatedapproaches to this problem, where state preparation, gate, and measurementerrors will need to decrease rapidly with $\kappa$ for worst-case and typicalinstances if error correction is not used, and present some open problems.

Complexity of quantum state verification in the quantum linear systems problem