论文标题
量子线性系统问题中量子状态验证的复杂性
Complexity of quantum state verification in the quantum linear systems problem
论文作者
论文摘要
我们在求解表单$ a \ vec x = \ vec b $的线性方程系统的上下文中分析了量子状态验证的复杂性。我们表明，任何验证给定量子状态是否距离量子线性系统问题的恒定距离内的量子操作都需要$ q =ω（κ）$的使用，以准备量子状态$ \ left | b \ right> $，与$ \ vec b $成比例，在最坏情况下它的逆向。在这里，$κ$是矩阵$ a $的条件数。对于典型的情况，我们表明$ q =ω（\sqrtκ）$具有很高的可能性。如果使用已知的量子算法进行量子线性系统问题，则几乎可以实现这些下限。我们还分析了$ \ left |的副本数量b \ right> $由准备和测量类型的验证过程要求。在这种情况下，在最坏情况下，下限在$ω（κ^2）$，在典型情况下为$ω（κ）$的$ω（κ^2）$更糟。我们讨论了结果对已知的变异和相关方法的含义，在此问题中，如果不使用错误校正，则需要使用$κ$ $κ$迅速减少状态准备，门和测量错误，并提出一些开放问题。
We analyze the complexity of quantum state verification in the context of solving systems of linear equations of the form $A \vec x = \vec b$. We show that any quantum operation that verifies whether a given quantum state is within a constant distance from the solution of the quantum linear systems problem requires $q=Ω(κ)$ uses of a unitary that prepares a quantum state $\left| b \right>$, proportional to $\vec b$, and its inverse in the worst case. Here, $κ$ is the condition number of the matrix $A$. For typical instances, we show that $q=Ω(\sqrt κ)$ with high probability. These lower bounds are almost achieved if quantum state verification is performed using known quantum algorithms for the quantum linear systems problem. We also analyze the number of copies of $\left| b \right>$ required by verification procedures of the prepare and measure type. In this case, the lower bounds are quadratically worse, being $Ω(κ^2)$ in the worst case and $Ω(κ)$ in typical instances with high probability. We discuss the implications of our results to known variational and related approaches to this problem, where state preparation, gate, and measurement errors will need to decrease rapidly with $κ$ for worst-case and typical instances if error correction is not used, and present some open problems.
