Simultaneously optimal queries to both quantum linear-system oracles
- Field
- Topics
Problem
Can one quantum linear-system algorithm attain both query bounds in (2) simultaneously? Let \(A\in\mathbb{C}^{N\times N}\) be invertible, with exact block-encoding oracle \(O_A\) for \(A/\alpha_A\) and state-preparation oracle \(O_b\lvert0\rangle=\lvert b\rangle\). Given bounds \(\alpha_A\geq\lVert A\rVert\), \(\alpha_{A^{-1}}\geq\lVert A^{-1}\rVert\), define (1):
Assume a constant-factor estimate of \(p\) is supplied. For every \(0<\epsilon<1/2\), require a state \(\lvert\widetilde{x}\rangle\) with \(\lVert\lvert\widetilde{x}\rangle-\lvert x\rangle\rVert\leq\epsilon\), with success probability at least \(2/3\), using
Queries include inverse and controlled oracle calls; constants must be uniform over admissible inputs.
Source
Low and Su, Section 7, Eq. (241), with the supplied-norm-estimate convention of Theorem 2 [LS26].
Progress
Theorem 2 achieves \(Q_b=O(p^{-1/2})\) and \(Q_A=O(KL\log(L/\epsilon))\), where \(L=\max\{1,\log(p^{-1/2})\}\). Theorem 4 achieves \(Q_A=O(K\log(1/\epsilon))\) with \(Q_b=O(K\log(1/\epsilon))\) [LS26].
Theorem 3 proves a worst-case \(\Omega(p^{-1/2})\) state-preparation lower bound when the inverse-norm bound is tight [LS26].
Comment
The gap is simultaneous attainment, not either bound separately. \(K\) bounds the spectral condition number. Estimating an initially unknown \(p\) is a separate resource question.