A shortcut to an optimal quantum linear system solver

Alexander M. Dalzell

AWS Center for Quantum Computing, Pasadena, CA

Given a linear system of equations $A\vec{x} = \vec{b}$, quantum linear system solvers (QLSSs) approximately prepare a quantum state $\ket{\vec{x}}$ for which the amplitudes are proportional to the solution vector $\vec{x}$. Asymptotically optimal QLSSs have query complexity $O(\kappa \log(1/\varepsilon))$, where $\kappa$ is the condition number of $A$, and $\varepsilon$ is the approximation error. However, runtime guarantees for existing optimal and near-optimal QLSSs do not have favorable constant prefactors, in part because they rely on complex or difficult-to-analyze techniques like variable-time amplitude amplification and adiabatic path-following. Here, we give a conceptually simple QLSS that does not use these techniques. If the solution norm $\nrm{\vec{x}}$ is known exactly, our QLSS requires only a single application of kernel reflection—a straightforward extension of the eigenstate filtering (EF) technique of previous work—and the query complexity of the QLSS is $(1+O(\varepsilon))\kappa \ln(2\sqrt{2}/\varepsilon)$.
If the norm is unknown, our method allows it to be estimated up to a constant factor using $O( \log\log(\kappa))$ applications of kernel projection—a direct generalization of EF—yielding a straightforward QLSS with near-optimal $O(\kappa \log\log(\kappa)\log\log\log(\kappa)+\kappa\log(1/\varepsilon))$ total complexity. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(\kappa)$ complexity can be achieved for estimating the norm up to a constant factor, yielding an optimal QLSS with $O(\kappa\log(1/\varepsilon))$ complexity while still avoiding the need to analyze the adiabatic theorem. Finally, we give explicit upper bounds on the constant prefactors of the complexity statements: we show that the query complexity of our optimal QLSS is at most $56\kappa + 1.05\kappa \ln(1/\varepsilon) + o(\kappa)$, saving more than an order of magnitude compared to existing QLSS complexity guarantees.

§ INTRODUCTION

Quantum linear system solvers (QLSSs) efficiently produce a quantum state $\ket{\vec{x}}$ that encodes the solution to a linear system of equations, $A\vec{x} = \vec{b}$.
Since their discovery in 2009 <cit.>, they have been a key driver of enthusiasm for quantum computing. After all, the need to numerically solve large linear systems appears in a multitude of applications and already represents a key use case for advanced classical computational hardware, such as graphical processing units. However, compared to their classical counterparts, quantum algorithms begin at an orders-of-magnitude disadvantage due to slower physical clock speeds and severe overheads from quantum error correction (see, e.g., <cit.>). Thus, providing a substantial quantum speedup with the QLSS will require making optimizations at every level of the computational stack.

Toward this end, the asymptotic performance of the QLSS has been steadily improved over time. The key parameters that determine the QLSS complexity are the condition number
$\kappa$ of the matrix to be inverted—that is, the ratio of its largest and smallest singular value—and the error $\varepsilon$ sought by the solution. The original QLSS had cost $O(\kappa^2/\varepsilon)$ queries to the input data comprising $A$ and $\vec{b}$ <cit.>. A sequence of improvements <cit.> has reduced this complexity to $O(\kappa \log(1/\varepsilon))$ <cit.>, which matches lower bounds showing that linear-in-$\kappa$ is optimal <cit.>.[It has additionally been claimed <cit.> that $O(\kappa\log(1/\varepsilon))$ is jointly optimal in both $\kappa$ and $1/\varepsilon$, based on forthcoming work by Kothari and Harrow. However, at the time of this writing, we are not aware of a publicly available proof of this fact. In this paper, unless otherwise stated, when we write “optimal” and “near-optimal” we mean only with respect to $\kappa$, where near-optimal refers to scaling $\kappa \, \mathrm{polylog}(\kappa)$. ]

[scale=1.26,thick,baseline=0mm,bezier bounding box]

(A) at (-/2-*/+,-/2);
(B) at (-/2+,/2);
(C) at (/2+*/+,/2);
(D) at (/2+,-/2);
rwpath/.style=red, very thin, decorate, decoration = random steps, segment length=1.5pt, amplitude=0.7pt
[draw=none,fill=bkgray] (A)–(B)–(C)–(D)–cycle;

(E) at (0,);
(F) at (*, *);
(G) at (*2**,**-**);
(H) at (,0);
(I) at (-*0.8*,-*0.8*);

[rwpath] (H) arc(0:-90:+ *0.8* and *0.8*);

[black, thick, ->] (0,0) – (E);
[black, ->] (0,0) – (F);
[black, ->] (0,0) – (G);
[black, ->] (0,0) – (H);
[black, ->] (0,0) – (I);
[black,densely dashed,very thin] (H) arc[start angle=0, end angle=90, radius=];

at (*1.25,0) $\ket{\vec{x}}$;
at (0,*1.22) $\ket{\vec{e_n}}$;
at (**1.25+0.1,**1.25-0.03) $\ket{\vec{x_t}}$;
at (-*0.8**1.25,-*0.8**0.9) $\ket{\vec{s}}$;
at (1.25**2**+*0.65,1.25***-1.25***-0.07) $\cos(2\theta_t)\ket{\vec{e_n}} + \sin(2\theta_t)\ket{\vec{x}}$;

[ultra thin, black] (*2**,**-**) arc(90-2*:90:);
at (**1.25,**1.25) $\theta_t$;
at (***1.25+***1.25,***1.25-***1.25) $\theta_t$;

Illustration of the conceptual idea of our quantum linear system solver.  Roughly speaking, previous methods approximately follow an adiabatic path from an initial state $\ket{\vec{s}}$ to the solution $\ket{\vec{x}}$, depicted by the red line, and then refine the resulting state with eigenstate filtering (EF). In contrast, our method begins in a known state $\ket{\vec{e_n}}$ that is deliberately orthogonal to $\ket{\vec{x}}$. Given an estimate $t$ for $\nrm{\vec{x}}$, it uses the quantum singular value transformation (QSVT) to reflect about the solution $\ket{\vec{x_t}}$ to an augmented linear system, arriving at $\cos(2\theta_t)\ket{\vec{e_n}}+ \sin(2\theta_t)\ket{\vec{x}}$, where $\theta_t = \arctan(\nrm{\vec{x}}/t)$ is the initial angle between $\ket{\vec{e_n}}$ and $\ket{\vec{x_t}}$. Then, it projects onto the image of $I-\ketbra{\vec{e_n}}$ (shaded plane) with success probability $sin^2(2θ_t)$, to arrive at $|x⃗⟩$, up to errors induced by imperfect reflection. The success probability is $Ω(1)$ as long as $t$ is a constant-factor approximation of $x⃗$. }
\label{fig:two_step}
\end{figure}

The optimal QLSS of Ref.~\cite{costa2021OptimalLinearSystem} achieves this state-of-the-art complexity by combining two techniques: (i) \textit{eigenstate filtering} (EF), and (ii) \textit{adiabatic path-following} via the ``quantum walk method.'' It utilizes EF \cite{lin2019OptimalQEigenstateFiltering} to approximately project onto the ideal state $|x⃗⟩$ at cost $O(κlog(1/ε))$. However, to apply this technique, one must first prepare an ansatz state $|x⃗_⃗a⃗n⃗s⃗⟩$ that has constant overlap $γ= |⟨x⃗_⃗a⃗n⃗s⃗|x⃗⟩| = Ω(1)$, so that EF succeeds with substantial probability, and need not be repeated more than $1/γ^2 = O(1)$ times on average. Extending ideas first explored in Refs.~\cite{subasi2019QAlgSysLinEqsAdiabatic,an2022QLSStimeDepAdiabatic}, this ansatz state is prepared by applying a sequence of unitary ``walk'' operators, where the eigenstates of the operators follow a smoothly varying ``eigenpath''---the discrete adiabatic theorem guarantees that if the path is traversed sufficiently slowly, the state of the system will approximately track the eigenpath. For the QLSS, one chooses the sequence of walk operators so that the path begins at a simple-to-prepare state related only to the vector $b⃗$. As the sequence progresses, information about $A$ is introduced, and the path ends at a state from which $|x⃗⟩$ can be easily extracted.  Ultimately, the method prepares a state $|x⃗_⃗a⃗n⃗s⃗⟩$ achieving overlap $γ$ at total cost $O(κ/√(1-γ^2))$.

However, rigorous treatment of adiabatic algorithms are notoriously difficult \cite{albash2018AQCreview}. Accordingly, the analysis of the discrete adiabatic theorem in Ref.~\cite{costa2021OptimalLinearSystem} is intricate and introduces a large constant prefactor, on the order of $10^5$ (see \cite[Eq.~(L2)]{jennings2023QLSS}), into the rigorous bound on the complexity of preparing the ansatz state via the quantum walk method. A rigorous analysis \cite{jennings2023QLSS} of an alternative adiabatic path-following strategy called the ``randomization method'' \cite{subasi2019QAlgSysLinEqsAdiabatic} has a similar conclusion: ansatz state preparation is far more costly than the subsequent EF step, even for very small values of $ε$.
This large cost of the QLSS---and in particular ansatz state preparation---contributes to the large resource estimates reported for QLSS-based applications, such as financial portfolio optimization \cite{dalzell2022socp} and solving differential equations \cite{jennings2023costDiffEQ}.
Numerical simulations \cite{costa2023discreteConstantFactors} on small random linear systems of size up to $16 ×16$ suggest that for both the randomization method and the quantum walk method, the constant prefactors involved are much smaller than their explicit upper bounds. Nevertheless, it remains desirable to have a tighter upper bound that is guaranteed to hold for larger systems, and in the worst case.

In this paper, we introduce a new conceptual idea, depicted in \autoref{fig:two_step}, that eliminates the need for ansatz state preparation via adiabatic path-following. Briefly, the idea is to \textit{augment} the linear system by adding a single additional variable and a single uncoupled constraint on that variable. The solution to the augmented linear system simultaneously has constant overlap with the solution $|x⃗⟩$ and with an easy-to-prepare state we label $|e⃗_⃗n⃗⟩$. Thus, we can quickly navigate from $|e⃗_⃗n⃗⟩$ to $|x⃗⟩$ by approximately reflecting about the solution to the augmented system---implementing this reflection is an extension of the EF technique and has cost  $O(κlog(1/ε))$. The result is a simper QLSS that relies only on EF-like operations combined with a few straightforward linear algebra observations.

A caveat is that augmenting the linear system in the right way requires knowing (or guessing) an estimate of the Euclidean norm $x⃗$ of the solution to the linear system. Thus, in a sense, our work might be viewed as \textit{replacing} the ansatz-state-preparation step in prior QLSSs with a solution-norm-estimation step. This trade is beneficial since $x⃗$ is a single real number that need only be learned once, rather than a high-dimensional quantum state that must be reprepared each time the linear system is to be solved. If the norm is known to within a constant multiplicative factor, our QLSS is asymptotically optimal, with $O(κlog(1/ε))$ cost. If the norm is unknown, we also show that our framework offers a simple way to learn it (up to a constant factor) in near-optimal cost $O(κloglog(κ)logloglog(κ))$.
Alternatively, by using our method together with some of the intuition from the adiabatic approach, we show that the norm can be learned up to a constant factor in optimal $O(κ)$ complexity, while still avoiding the intricate analysis of the adiabatic theorem.
Furthermore, the approximation ratio of the norm estimate can be improved from constant to $1+ε$ incurring additional  cost equal to $O(κlog(1/ε)/ε)$, shaving multiple $log(κ)$ and $log(1/ε)$ factors off of the previous state-of-the-art method for norm estimation from Ref.~\cite{chakraborty2018BlockMatrixPowers}, and nearly matching the lower bound of $Ω(κ/ε)$ that we show in the appendix.  Depending on which norm estimation method is used, this gives a full QLSS with optimal or near-optimal query complexity.

In \autoref{sec:QLSP}, we establish notation and background information about the quantum linear system problem, and in \autoref{sec:KP_KR_main} we introduce \textit{kernel projection} and \textit{kernel reflection}, the EF-like operations that constitute the main technical ingredient of our QLSS. In \autoref{sec:QLSS_given_norm_main}, we present our main algorithm for solving the quantum linear system problem when an estimate for the solution norm is known, and in \autoref{sec:estimating_the_norm}, we present several algorithms for estimating the norm, along with compact, non-optimized proofs of correctness. In \autoref{sec:constant_factors}, we provide a discussion of constant prefactors, based on a more detailed version of our QLSS that we develop in the appendix.  Finally, in \autoref{sec:conclusion} we provide some concluding remarks.

\section{The quantum linear system problem}\label{sec:QLSP}

The input to the linear system problem is an $m ×n$ matrix $A ∈ℂ^m×n$ and a vector $b⃗ ∈ℂ^m$.
The solution is a vector $x⃗ ∈ℂ^n$ for which $Ax⃗ = b⃗$, assuming such a solution exists.\footnote{If no solution exists (because $\vec{b}$ is not in the column space of $A$), we ideally seek the vector for which the least-squares metric $\nrm{A\vec{x} - \vec{b}}$ is minimized. However, our QLSS does not offer a solution in this case, and throughout we assume that $\vec{b}$ is in the column space of $A$. The least-squares case can be handled by the near-optimal QLSS of Ref.~\cite{chakraborty2018BlockMatrixPowers}.}
When more than one such solution exists, we seek the $x⃗$ with minimum Euclidean norm $x⃗$.

Let $s = ⌈log_2(1+max(m,n))⌉$ (here we add one to leave room for an extra row/column, as discussed later). Consider an $s$-qubit system with orthonormal computational basis states ${|e⃗_⃗j⃗⟩}_j=0^2^s-1$. For $k ≤2^s$, we associate $k$-dimensional vectors $u⃗ = (u_0,…,u_k-1)∈ℂ^k$ with normalized $s$-qubit states $|u⃗⟩ = u⃗^-1∑_j=0^k-1 u_j|e⃗_⃗j⃗⟩$, for which the coefficients in the computational basis are proportional to the corresponding vector entries. For $k_r,k_c ≤2^s$, we associate $k_r ×k_c$ matrices $M$ with the operator $∑_i=0^k_r-1∑_j=0^k_c-1 m_ij e⃗_⃗i⃗e⃗_⃗j⃗$, where $m_ij$ are the matrix entries of $M$. Then, following standard conventions, we assume we have access to the data in the $n$-dimensional vector $b⃗$ via a unitary operator $U_b⃗$ for which $U_b⃗|e⃗_⃗0⃗⟩=|b⃗⟩$. We also assume that $A ≤1$ (where $·$ denotes spectral norm for matrix arguments),  and that we have access to the matrix $A$ via a $(α,a)$-block-encoding of $A$, that is, an $(a+s)$-qubit unitary operation $U_A$ for which
\begin{equation} \nonumber
A =  \alpha(\bra{0}^{\otimes a} \otimes I_{2^s})U_A (\ket{0}^{\otimes a} \otimes I_{2^s})
\end{equation}
where $I_d$ denotes the identity operator on a Hilbert space of dimension $d$, here the Hilbert space for the $s$-qubit system. Note that unitarity requires $α≥A$, where $·$ for matrix arguments denotes spectral norm.

The quantum linear system problem (QLSP) takes as input an error parameter $ε$ and asks to produce a quantum state $|x⃗̃⃗⟩$ for which the trace distance $1/2|x⃗⟩⟨-||x⃗̃⃗⟩⟨|_1$ is at most $ε$, while minimizing the number of queries to $U_A$ and $U_b⃗$, as well as their controlled versions and their inverses. We also accept randomized algorithms that output a mixed state $ρ̃$ for which  $1/2|x⃗⟩⟨-|ρ̃_1≤ε$. Our analysis could have been performed for other related metrics, such as $|x⃗⟩-|x⃗̃⃗⟩$, as used in Ref.~\cite{costa2021OptimalLinearSystem}.
% \footnote{The metric $\nrm{\ket{\vec{x}}- \ket{\vec{\tilde{x}}}}$ is sensitive to the global phase of $\ket{\vec{\tilde{x}}}$ and thus leads to a stronger requirement on the QLSP compared to the metric $\frac{1}{2}\nrm{\ketbra{\vec{x}}-\ketbra{\vec{\tilde{x}}}}_1$. In the most straightforward applications of the QLSP, this global phase is unphysical. However, in some applications, such as those that require learning the amplitudes of $\ket{\vec{\tilde{x}}}$ with quantum state tomography \cite{kerenidis2018QIntPoint,dalzell2022socp, apeldoorn2022TomographyStatePreparationUnitaries}, the global phase is important. In general, when one performs a controlled QLSS, the unphysical global phase turns into a physical controlled phase (i.e., a single-qubit rotation on the control qubit). }

Additionally, henceforth we assume the convention that $b⃗ = 1$ and $α=1$.  This convention is also without loss of generality since the quantum linear system problem asks only to prepare a quantum state proportional to $x⃗$, making it insensitive to scaling of $A$ and $b⃗$. We suppose there is a known value of $κ$ such that all nonzero singular values of $A$ fall in the interval $[κ^-1,1]$---thus $κ$ is an upper bound on the condition number of $A$, when $A$ is restricted to act on inputs orthogonal to its kernel. These conventions imply that
\begin{equation}
1 \leq \nrm{\vec{x}} \leq \kappa\,.
\end{equation}

\section{Kernel projection and kernel reflection}\label{sec:KP_KR_main}

Kernel projection (KP) is the term we give to the technique of eigenstate filtering, generalized to non-Hermitian and potentially non-square matrices. As its name suggests, when combined with postselection, it leads to approximate projection onto the kernel of a matrix. Similarly, kernel reflection (KR) leads to approximate reflection about the kernel. In either case, the first step is to construct a matrix $G$ out of $A$ and $b⃗$ for which $x⃗$ is in the kernel. Namely, following prior work \cite{subasi2019QAlgSysLinEqsAdiabatic,an2022QLSStimeDepAdiabatic,lin2019OptimalQEigenstateFiltering}, we let
\begin{equation}\label{eq:G}
G = Q_{\vec{b}}A
\end{equation}
where the $m ×m$ matrix $Q_b⃗ = I_m - b⃗b⃗^†$
is the projector onto the subspace orthogonal to $b⃗$. The kernel of $G$ is the span of the kernel of $A$ and the vector $x⃗$. Here, we note that since we have defined $x⃗$ to be the solution to $Ax⃗ = b⃗$ of minimum norm $x⃗$, $x⃗$ is orthogonal to the kernel of $A$.  We can easily construct a $(1,a+1)$-block-encoding $U_G$ for $G$ using one query to each of $U_A$, $U_b⃗$, and $U_b⃗^†$; see \autoref{app:block_encodings}.

Furthermore, we can assert that the smallest nonzero singular value of $G$ is at least $κ^-1$, by the following argument (see also  \cite{subasi2019QAlgSysLinEqsAdiabatic,an2022QLSStimeDepAdiabatic}). Suppose $σ$ is a nonzero singular value of $G$, with normalized left singular vector $u⃗$ and right singular vector $v⃗$. Since $σ$ is nonzero, $v⃗$ is orthogonal to $x⃗$ and to the kernel of $A$. Moreover, by definition of singular vectors, $σu⃗ = Q_b⃗ A v⃗ = Av⃗ - (b⃗^†Av⃗)b⃗ = A(v⃗ - (b⃗^†Av⃗)x⃗)$, implying that $u⃗$ is in the image of $A$, and also that $Q_b⃗ u⃗ = u⃗$.  By the definition of singular values, $σ^2 = u⃗^†Q_b⃗ A A^†Q_b⃗ u⃗ = u⃗^†AA^†u⃗≥1/κ^2$, where the last inequality follows from the fact that $u⃗$ is in the image of $A$, and thus can be expressed as a linear combination of eigenvectors of $AA^†$, all of which have eigenvalue at least $1/κ^2$.

With these facts established, we can now define the technique of kernel projection. It takes as input two parameters $(κ,η)$ and only works under the promise that the nonzero singular values of $G$ lie in the interval $[κ^-1,1]$ (which we proved above in the case $G=Q_b⃗A$). Consider an arbitrary normalized $s$-qubit state $|ϕ⟩ = γ|w⃗⟩ + ν|w⃗_⃗⊥⃗⟩$, where $w⃗$ is a unit vector in the kernel of $G$ (typically $|w⃗⟩ = |x⃗⟩$), and $w⃗_⃗⊥⃗$ is a unit vector orthogonal to the kernel of $G$. KP enacts the transformation
\begin{equation}\label{eq:impact_KP}
\gamma \ket{\vec{w}} + \nu \ket{\vec{w}_{\perp}} \overset{\rm KP}{\mapsto} \gamma \ket{\vec{w}} + \nu\delta_1\ket{\vec{w_{\perp}}}+\nu\delta_2\ket{\vec{w_{\perp}'}}
\end{equation}
where $δ_1$ and $δ_2$ are real parameters (dependent on $w⃗$), that satisfy $√(δ_1^2+δ_2^2)≤η$, and $w⃗_⃗⊥⃗'⃗$ is another unit vector orthogonal to $w⃗_⃗⊥⃗$ and to the kernel of $G$. In other words, KP leaves the kernel of $G$ untouched while shrinking the norm of the portion of the state orthogonal to the kernel by a factor of $η$ (or more). The right-hand side is subnormalized: the probability that KP succeeds is given by its squared-norm $|γ|^2+|ν|^2(δ_1^2+δ_2^2)$. This probability can be small if the initial state $|ϕ⟩$ has small overlap $γ$ with the kernel of $G$, necessitating the step of ansatz state preparation in prior work \cite{lin2019OptimalQEigenstateFiltering,costa2021OptimalLinearSystem}.

Similarly, KR can be understood as enacting the transformation
\begin{equation}\label{eq:impact_KR}
\gamma \ket{\vec{w}} + \nu \ket{\vec{w}_{\perp}} \overset{\rm KR}{\mapsto} \gamma \ket{\vec{w}} - \nu(1-\delta_1')\ket{\vec{w_{\perp}}}+\nu\delta_2'\ket{\vec{w_{\perp}'}}\,.
\end{equation}

\noindent For fixed $w⃗$ and $w⃗_⃗⊥⃗$, the vector $w⃗_⃗⊥⃗'⃗$ in Eq.~\eqref{eq:impact_KR} is the same as the one in Eq.~\eqref{eq:impact_KP}. Moreover, we have the identities $δ_1' = 2η+2δ_1/1+η$ and $δ_2' = 2δ_2/1+η$, from which we can derive relations
\begin{equation}\label{eq:delta_deltaprime_relations}
\delta_1' \geq 0, \;\;\;  \sqrt{\delta_1'^2+\delta_2'^2} \leq \frac{4\eta}{1+\eta}, \;\;\; |\delta'_2|\leq \frac{2\eta}{1+\eta}
\end{equation}
These identities are justified in \autoref{app:KP_KR}, and follow from the close relationship between KP and KR.
Namely, both KP and KR are enacted as an application of the quantum singular value transformation (QSVT) \cite{gilyen2018QSingValTransf, martyn2021GrandUnificationQAlgs}. Briefly, the QSVT procedure involves preparing the state $|0⟩^⊗(a+2) ⊗|ϕ⟩$, applying a sequence of gates including $U_G$ and $U_G^†$, and then postselecting on the first register being $|0⟩^⊗(a+2)$---success or failure of KP and KR is heralded by the outcome of these measurements. The circuit is constructed to preserve the right singular vectors of $G$ while applying a certain polynomial transformation to the singular values, and the total cost of the procedure scales with the degree of the polynomial. To perform KP, we choose a polynomial $p$ for which $p(0)=1$ and $|p(x)| ≤η$ for all $x ≥κ^-1$. To perform KR, we choose a related polynomial where $p(0) = 1$ and $-1≤p(x) ≤-1+4η/(1+η)$ for all $x ≥κ^-1$.
In both cases, the degree of this polynomial is $2ℓ$, where
\begin{equation}
\ell = \lceil \kappa \ln(2/\eta)/2\rceil
\end{equation}
The cost of implementing the KP or KR unitary is $ℓ$ calls to the block-encoding $U_G$, $ℓ$ calls to its inverse $U_G^†$,  $4ℓ$ multi-controlled Toffoli gates, and $2ℓ$ single-qubit rotation gates.
Details of this implementation can be found in \autoref{app:KP_KR}.

KP is equivalent to EF when the matrix $A$ is Hermitian. EF was developed in Ref.~\cite{lin2019OptimalQEigenstateFiltering}, where it was applied to the QLSP to give the first QLSS with error dependence strictly linear in $log(1/ε)$. The idea was to use existing QLSSs to first produce a state $|x⃗_⃗a⃗n⃗s⃗⟩$ with $γ= Ω(1)$ overlap with $|x⃗⟩$, and then apply EF to project to a state $ε$-close to $|x⃗⟩$, succeeding with probability roughly $|γ|^2$. Later, Ref.~\cite{costa2021OptimalLinearSystem} showed that a QLSS based on the discrete adiabatic theorem can produce a state $|x⃗_⃗a⃗n⃗s⃗⟩$ with $O(κ/√(1-γ^2))$ complexity, which, combined with EF and taking $γ= Ω(1)$, gives an optimal QLSS with overall $O(κlog(1/ε))$ complexity.

% \section{Algorithms}\label{sec:algorithms}

\section{Optimal QLSS given constant-factor estimate for norm}\label{sec:QLSS_given_norm_main}

The main conceptual idea presented in this paper is to form an augmented linear system by introducing one new variable to the system, and adding one new (uncoupled) linear constraint involving that variable. This adds a known singular vector to the linear system, with a known, tunable singular value. If the known singular value is chosen appropriately, then the solution to the augmented linear system simultaneously has substantial overlap with the solution $|x⃗⟩$ of the original linear system, and with the known singular vector. This produces a navigable path from the known singular vector to the solution $|x⃗⟩$ that bypasses the need for sophisticated ansatz-preparation methods---a shortcut to an optimal QLSS.

Recall that $b⃗ = 1$ and $A ≤1$ by convention, and that this implies that $1 ≤x⃗ ≤κ$. Let $t ∈[1,κ]$ be an estimate of $x⃗$ and define
\begin{equation}
\theta_t = \arctan\left(\frac{\nrm{\vec{x}}}{t}\right)\,.
\end{equation}
Let $A_t$ be an $(m+1)×(n+1)$ matrix, where the upper left $m ×n$ block is $A$, the lower right entry is $1/t$, and the other entries are zero:
\begin{equation}\label{eq:A_t}
A_t = A + \frac{1}{t}\vec{e}_m \vec{e_n}^\dagger =
\begin{bmatrix}
A & 0 \\
0 & t^{-1}
\end{bmatrix}\,.
\end{equation}
All nonzero singular values of $A_t$ lie in the interval $[κ^-1,1]$.
Furthermore, define
\begin{equation}
\vec{b'} = \frac{1}{\sqrt{2}}\left(\vec{b} + \vec{e_m}\right) =
\begin{bmatrix}
\vec{b}/\sqrt{2} \\
\end{bmatrix}
\end{equation}
It is then easy to verify that the solution to the augmented system $A_tx⃗_⃗t⃗ = b⃗'⃗$ is
\begin{equation}
\vec{x_t} = \frac{1}{\sqrt{2}}\left(\vec{x} + t \vec{e_n}\right) =
\begin{bmatrix}
\vec{x} /\sqrt{2}\\
t / \sqrt{2}
\end{bmatrix} \,.
\end{equation}
The vectors $x⃗$, $x⃗_⃗t⃗$, and $e⃗_⃗n⃗$ are depicted in \autoref{fig:two_step}. All three lie in the plane spanned by $x⃗$ and $e⃗_⃗n⃗$ with $θ_t$ the angle between $e⃗_⃗n⃗$ and $x⃗_⃗t⃗$.

With one ancilla qubit and one controlled query to $U_b⃗$, we can easily construct a unitary $U_b⃗'⃗$ that prepares $|b⃗'⃗⟩$. Similarly, with one controlled query to $U_A$, we can construct a $(1,a+1)$-block-encoding $U_A_t$ for $A_t$. This block-encoding can be turned into a $(1, a+2)$-block-encoding $U_G_t$ of the matrix  (cf.~Eq.~\eqref{eq:G})
\begin{equation}\label{eq:G_t}
G_t = Q_{\vec{b'}}A_t
\end{equation}
for which $x⃗_⃗t⃗$ lies in the kernel, and the nonzero singular values are contained in $[κ^-1,1]$; these block-encoding constructions are provided in \autoref{app:block_encodings}.

Our main algorithm proposes to begin in the state $|e⃗_⃗n⃗⟩$ and end in the orthogonal state $|x⃗⟩$. In this journey through the $n$-dimensional Hilbert space, the vector $|x⃗_⃗t⃗⟩$ is the essential landmark that charts the correct path. The QSVT-based technique of KR provides the vehicle for traversing this path, using the matrix $G_t$ as its compass, as $G_t$ encodes $|x⃗_⃗t⃗⟩$ into its kernel. As we will see, KR is most effective when the state $|x⃗_⃗t⃗⟩$ lies equally far from $|e⃗_⃗n⃗⟩$ and $|x⃗⟩$, corresponding to $θ_t = π/4$. If $θ_t$ is larger or too smaller, the algorithm requires more repetitions due to reduced success probability.

Formally, the algorithm takes as input the value of $κ$, as well as a choice for $t ∈[1,κ]$ and for $η∈(0,1]$. The procedure has three steps, described in \autoref{algo:main_algo}.

\SetKwInput{Input}{Input}
\SetKwInput{Output}{Output}
\SetKwInput{QCost}{Query Cost}
\SetKwInput{Set}{Set}
\SetKwFunction{ApprSolve}{ApprSolve}
\SetStartEndCondition{ }{}{}%
\SetKwProg{Fn}{def}{\string:}{}
\SetKwFunction{Range}{range}%%
\SetKw{KwTo}{in}\SetKwFor{For}{for}{\string:}{}%
\SetKwIF{If}{ElseIf}{Else}{if}{:}{elif}{else:}{}%
\SetKwFor{While}{while}{:}{fintq}%
\newcommand{\forcond}{$i$ \KwTo\Range{$n$}}
\AlgoDontDisplayBlockMarkers\SetAlgoNoEnd\SetAlgoNoLine%
\setlength{\algomargin}{1em}
\begin{algorithm}
\caption{QLSS given norm estimate }\label{algo:main_algo}
\DontPrintSemicolon
\SetAlgoLined
\LinesNumbered
\Input{$(A, \vec{b}, \kappa, \eta, t)$}
\Output{$\ket{\vec{\tilde{x}}}$ with probability $p_{\rm succ}$, or ``fail'' with probability $1-p_{\rm succ}$}
\BlankLine
Prepare $\ket{\vec{e_n}}$ \;
Apply KR to approximately reflect about the kernel of $G_t$ (defined in Eq.~\eqref{eq:G_t}), with parameters $(\kappa,\eta)$. If KR fails, output ``fail.''\;
Project onto $\spn\{\ket{\vec{e_j}}\}_{j=0}^{n-1}$ to produce $\ket{\vec{\tilde{x}}}$, by measuring the operator $I-\ketbra{\vec{e_n}}$. If projection fails, output ``fail.''\;
\end{algorithm}
We now analyze each step of this algorithm. The state prepared in step 1 can be decomposed as
\begin{equation}
\ket{\vec{e_n}} = \cos(\theta_t)\ket{\vec{x_t}} + \sin(\theta_t)\ket{\vec{y_t}}
\end{equation}
\begin{align}
\ket{\vec{x_t}} &= \phantom{-}\sin(\theta_t)\ket{\vec{x}} + \cos(\theta_t)\ket{\vec{e_n}}\,, \\
\ket{\vec{y_t}} &= -\cos(\theta_t)\ket{\vec{x}} + \sin(\theta_t)\ket{\vec{e_n}}
\end{align}
are orthogonal states. Since $\ket{\vec{x_t}}$ is in the kernel of $G_t$ and $\ket{\vec{y_t}}$ is orthogonal to $\ket{\vec{x_t}}$ and to the kernel of $A_t$ (to see this, observe that both $\ket{\vec{x}}$ and $\ket{\vec{e_n}}$ are orthogonal to the kernel of $A_t$), we can assert that $\ket{\vec{y_t}}$ is orthogonal to the kernel of $G_t$. Thus, we may invoke Eq.~\eqref{eq:impact_KR}, and we find that step 2 sends this state to
\begin{equation}\label{eq:post-step2}
\cos(\theta_t)\ket{\vec{x_t}} -(1-\delta'_1)\sin(\theta_t)\ket{\vec{y_t}} +  \delta'_2 \sin(\theta_t)\ket{\vec{z}}
\end{equation}
where $\delta_1'$ and $\delta_2'$ obey Eq.~\eqref{eq:delta_deltaprime_relations}. The state $\ket{\vec{z}}$ is a unit vector orthogonal to $\ket{\vec{x_t}}$ and $\ket{\vec{y_t}}$, and therefore orthogonal to $\ket{\vec{x}}$ and $\ket{\vec{e_n}}$.
Step 3 filters out $\ket{\vec{e_n}}$, bringing the state to
\begin{equation}\label{eq:post-step3}
\ket{\vec{\tilde{x}}} \propto \cos(\theta_t)\sin(\theta_t)(2-\delta'_1)\ket{\vec{x}} + \delta'_2 \sin(\theta_t)\ket{\vec{z}}\,.
\end{equation}

The probability that steps 2 and 3 both succeed, denoted by $p_{\rm succ}$, is given by the squared norm of the subnormalized state on the right-hand side of Eq.~\eqref{eq:post-step3}. Using Eq.~\eqref{eq:delta_deltaprime_relations}, it is seen to satisfy the bounds
\begin{equation}\label{eq:p_succ_bounds_main}
\sin^2(2\theta_t)\frac{\left(1-\eta\right)^2}{\left(1+\eta\right)^2} \leq p_{\rm succ} \leq \sin^2(2\theta_t) + \frac{4\eta^2}{(1+\eta)^2}
\end{equation}
where the lower (upper) bound is generated by replacing $\delta'_1$ with its maximum (minimum) value and $\delta'_2$ with its minimum (maximum) value. The success probability is plotted in \autoref{fig:succ_prob} for $\eta \rightarrow 0$. Examining Eq.~\eqref{eq:post-step3}, the normalized state $\ket{\vec{\tilde{x}}}$ is seen to satisfy
\begin{align}
\frac{1}{2}\nrm{\ketbra{\vec{x}}-\ketbra{\tilde{\vec{x}}}}_1 &= \sqrt{1-|\braket{\vec{x}}{\vec{\tilde{x}}}|^2} \\
&= |\delta_2'|\sin(\theta_t)p_{\rm succ}^{-1/2}\\
&\leq \frac{\eta+ O(\eta^2)}{\cos(\theta_t)}
\end{align}
Actually, a more careful analysis, performed in \autoref{thm:QLSS_known_norm} of \autoref{app:QLSS_with_norm_estimate}, shows that the unspecified $O(\eta^2)$ term in the final line above is not necessary.

The cost of step 2 is $\ell = \lceil \kappa\ln(2/\eta)/2\rceil$ controlled queries to each of $U_A$ and$U_A^\dagger$, and $2\ell$ controlled queries to each of $U_{\vec{b}}$ and $U_{\vec{b}}^\dagger$, as well as $O(\ell)$ other gates. The cost of step 3 is a single multi-controlled Toffoli gate, which can be used to set an ancilla to 1 only if the state is $\ket{\vec{e_n}}$. See \autoref{fig:main_algo_circuit} in
\autoref{app:QLSS_with_norm_estimate} for more information on the implementation of the three steps.

If the norm estimate $t$ is a constant-factor approximation of $\nrm{\vec{x}}$---that is, $t \in [\beta^{-1}\nrm{\vec{x}}, \beta \nrm{\vec{x}}]$ for some $\kappa$-independent constant $\beta = O(1)$,  then $\sin^2(2\theta_t) =4\nrm{\vec{x}}^2t^2/(\nrm{\vec{x}}^2+t^2)^2 = \Omega(1)$ and $\cos(\theta_t) = t/\sqrt{\nrm{\vec{x}}^2+t^2} = \Omega(1)$. Setting $\eta = \Theta(\varepsilon)$, we conclude that the algorithm need only be repeated an expected $O(1)$ number of times to successfully produce an output, and once it does, the output state $\ket{\vec{\tilde{x}}}$ solves the QLSP to error $\varepsilon$. The total expected query complexity is
\begin{equation}
Q = O(\kappa\log(1/\varepsilon))\,.
\end{equation}
Furthermore, if $t$ is exactly equal to the norm $\nrm{\vec{x}}$, then $\sin(2\theta_t) = 1$ and $\cos(\theta_t) = 1/\sqrt{2}$, so we may choose $\eta = \varepsilon/\sqrt{2}$ and find that the expected total query complexity to $U_A$ and $U_A^\dagger$ is given by
\begin{equation}
Q = (1+O(\varepsilon))\kappa \ln(2\sqrt{2}/\varepsilon)\,.
\end{equation}
See \autoref{cor:known_norm_expected_complexity} of \autoref{app:QLSS_with_norm_estimate} for a more precise statement of the complexity in terms of the approximation ratio $\beta$.

\begin{figure}[h!]
\centering
\includegraphics[width=\columnwidth]{succ_prob.pdf}
\caption{Success probability of \autoref{algo:main_algo} and of the kernel projection protocol of Eq.~\eqref{eq:post-step2-KP}, as a function of the approximation ratio $t/\nrm{\vec{x}}$, in the limit that the precision parameter $\eta \rightarrow 0$.}
\label{fig:succ_prob}
\end{figure}

\section{Estimating the norm}\label{sec:estimating_the_norm}

To achieve $O(\kappa \log(1/\varepsilon))$  query complexity, \autoref{algo:main_algo} requires that the input parameter $t$ is chosen to approximate $\nrm{\vec{x}}$ up to a constant multiplicative factor. However, $\nrm{\vec{x}}$ is generally not known, other than that it lies in the interval $[1,\kappa]$. Note that the optimal and near-optimal QLSSs based on adiabatic path-following do not offer a straightforward way to also estimate $\nrm{\vec{x}}$---the ability to produce $\ket{\vec{x}}$ in optimal $O(\kappa)$ complexity is not alone sufficient for optimal norm estimation. For example, one could try estimating $\nrm{\vec{x}}$ by applying the block-encoding $U_A$ to the vector $\ket{0}^{\otimes a}\ket{\vec{x}}$, producing the state $\nrm{\vec{x}}^{-1}\ket{0}^{\otimes a}\ket{\vec{b}} +\ket{{\perp}}$, where $\ket{{\perp}}$ is a state for which $(\bra{0}^{\otimes a} \otimes I_{2^s})\ket{{\perp}} = 0$. The norm $\nrm{\vec{x}}$ could then be read out via overlap estimation \cite{knill2007ObservableMeasurement} with the state $\ket{0}^{\otimes a} \ket{\vec{b}}$. However, gaining a constant factor approximation to the overlap in this fashion requires $O(\nrm{\vec{x}})$ queries to the procedure that prepares $\ket{\vec{x}}$, for total complexity $O(\kappa\nrm{\vec{x}})$, which can be as large as $O(\kappa^2)$.

The QLSS based on the variable-time amplitude estimation technique provides a method to generate a $(1+\varepsilon)$-factor approximation for $\nrm{\vec{x}}$  in near-optimal $O(\kappa \varepsilon^{-1} \log^2(\kappa\varepsilon^{-1})\log^3(\kappa) \log\log(\kappa) )$ complexity \cite[Corollary 32]{chakraborty2018BlockMatrixPowers}. However, this still leaves considerable room for improvement, both in performance and in conceptual transparency. In contrast, our approach offers several immediate near-optimal options for estimating the norm.

\subsection{Exhaustive search in log space}\label{sec:estimate_norm_exhaustive_search}

The simplest method for norm estimation is an exhaustive search in log space: we can recognize when $t$ is a good approximation of $\nrm{\vec{x}}$ by the fact that \autoref{algo:main_algo} has high success probability---thus, we can simply run \autoref{algo:main_algo} on a geometrically increasing sequence of choices of $t$ until we have found one that leads to success.

We now provide a concrete implementation and compact proof of correctness for this approach. Suppose we seek a multiplicative $2$-approximation to $\nrm{\vec{x}}$. Equivalently, we may find an additive $\ln(2)$-approximation to $\chi = \ln(\nrm{\vec{x}})$. We consider the set
\begin{equation}\label{eq:T_candidates}
\mathcal{T} = \{0, \ln(2), 2\ln(2), \ldots, \lceil \log_2(\kappa) \rceil \ln(2)\}
\end{equation}
Let $\tau^*$ denote the element of $\mathcal{T}$ that is nearest to $\chi$, which is guaranteed to be an additive $\ln(2)/2$-approximation for $\chi$.
Since $\tau^*$ is an additive $\ln(2)/2$-approximation to $\chi$, we have $\sin^2(2\theta_{e^{\tau^*}}) = \frac{4e^{2\tau^*+2\chi}}{(e^{2\tau^*} + e^{2\chi})^2} \geq 8/9$ (see \autoref{fig:succ_prob}). Now, fix the precision parameter for \autoref{algo:main_algo} to $\eta = 0.025$, ensuring that $(1-\eta)^2/(1+\eta)^2 \geq 9/10$ and $4\eta^2/(1+\eta)^2 \leq 1/100$.
By Eq.~\eqref{eq:p_succ_bounds_main}, the success probability of \autoref{algo:main_algo} when $t = e^{\tau^*}$ satisfies $p_{\rm succ} \geq (8/9)(9/10) = 0.8$. Meanwhile, for any value of $\tau$ that is more than $\ln(2)$-far from $\chi$, we have $\sin^2(2\theta_{e^{\tau}}) < \frac{16}{25}$, and by Eq.~\eqref{eq:p_succ_bounds_main},  $p_{\rm succ} < \frac{16}{25}+\frac{1}{100} = 0.65$. Having established these bounds, we run \autoref{algo:main_algo}
\begin{equation}
k = \lceil 100 \ln(20|\mathcal{T}|) \rceil = O(\log\log(\kappa))
\end{equation}
times for each of the $|\mathcal{T}|$ candidate values of $\tau$, and by observing the fraction of times it succeeds, we compute an estimate $\tilde{p}_{\tau}$ of the success probability for each candidate. By Hoeffding's inequality, for all $\tau \in \mathcal{T}$, it holds that $\Pr[\tilde{p}_\tau - p_{\rm succ} \geq 0.075] \leq e^{-2(0.075)^2k} \leq 1/(20 |\mathcal{T}|)$, and similarly $\Pr[p_{\rm succ}-\tilde{p}_\tau \geq 0.075]$ satisfies the same bound. By the union bound, there is at most $0.05$ probability that either $p_{\tau^*} \leq 0.725$ or that $p_\tau \geq 0.725$ for some candidate $\tau$ that is not an additive $\ln(2)$-approximation to $\chi$. Thus, with probability 0.95, at least one of our estimates will satisfy $\tilde{p}_\tau > 0.725$ and if we output $t=e^\tau$ for the first $\tau$ we find for which this is the case, that value of $t$ will be a multiplicative $2$-approximation to $\nrm{\vec{x}}$. This proves that the output of the algorithm is a multiplicative $2$-approximation to $\nrm{\vec{x}}$ with high probability.

The total query complexity to controlled-$U_A$ and controlled-$U_A^\dagger$ is
\begin{equation}\label{eq:Q_exhaustive_nonoptimized}
Q = 2k|\mathcal{T}|\lceil \kappa\ln(2/\eta)/2\rceil = O(\kappa \log(\kappa) \log\log(\kappa))\,.
\end{equation}
In \autoref{lem:estimate_norm_random_t} of \autoref{app:estimating_norm}, we provide a more formal analysis of a slightly different implementation that achieves the same complexity, with better constant prefactors on the complexity.
This query complexity can be improved to $O( \kappa \sqrt{\log(\kappa)}\log\log(\kappa))$ by straightforwardly replacing the exhaustive search above with a Grover search \cite{grover1996QSearch,yoder2014FixedPointSearch}, which we analyze in \autoref{lem:estimate_norm_random_t_FPAA} of \autoref{app:estimating_norm}.

\subsection{Binary search in log space}\label{sec:estimate_norm_binary_search}

Furthermore, with a bit more thought, the query complexity can be made even closer to linear-in-$\kappa$ using a binary search for $\tau = \ln(t)$. Here, rather than running \autoref{algo:main_algo}, we use KP to detect if a candidate value of $\tau$ is too large or too small. Specifically, suppose we prepare the state $\ket{\vec{e_n}}$, as in step 1 of \autoref{algo:main_algo}, and then we run step 2 using KP in place of KR. Invoking Eq.~\eqref{eq:impact_KP}, we arrive at the state (cf.~Eq.~\eqref{eq:post-step2})
\begin{equation}\label{eq:post-step2-KP}
\cos(\theta_t)\ket{\vec{x_t}} + \sin(\theta_t)\delta_1 \ket{\vec{y_t}} + \sin(\theta_t)\delta_2 \ket{\vec{z}}
\end{equation}
where $\sqrt{\delta_1^2+\delta_2^2} \leq \eta$. The success probability $q_{\rm succ}$ of KP is given by the squared norm of the above state, which satisfies
\begin{equation}\label{eq:succ_prob_KP}
\cos^2(\theta_t) \leq q_{\rm succ} \leq \cos^2(\theta_t)  + \eta^2\sin^2(\theta_t)\,.
\end{equation}
The function $\cos^2(\theta_t)$ is plotted in \autoref{fig:succ_prob}; it is monotonically increasing on the relevant interval and equal to 1/2 exactly at $t=\nrm{\vec{x}}$. Thus, estimating the success probability $q_{\rm succ}$ of KP for a certain choice of $\tau = \ln(t)$ offers a mechanism for determining whether $\tau \geq \chi$ or $\tau < \chi$, enabling a (noisy) binary search.

We now provide a concrete implementation for this noisy binary search. Fix $\eta = \sqrt{1/8}$. We maintain a set $\mathcal{S}$ of ``active'' candidates, and initially set $\mathcal{S} = \mathcal{T}$. We choose $\tau$ to be the median of $\mathcal{S}$, and we round the median to the closest element of $\mathcal{S}$, breaking ties arbitrarily. We run KP
\begin{equation}
k = \lceil 72 \ln(40\lceil\log_{3/2}(|\mathcal{T}|)\rceil )\rceil  = O(\log\log\log(\kappa))
\end{equation}
times with $t=e^{\tau}$, and we compute an estimate $\tilde{q}$ for $q_{\rm succ}$ based on the fraction of these $k$ trials that succeed. If $\tilde{q} > 1/2$, we eliminate all elements of $\mathcal{S}$ less than $\tau$; otherwise we eliminate all elements greater than $\tau$.
As long as $|\mathcal{S}|>2$, we are guaranteed to eliminate at least $1/3$ fraction of the elements. We repeat the process of choosing $\tau$ to be the median of $\mathcal{S}$, estimating $\tilde{q}$, and eliminating part of $\mathcal{S}$, a total of $\lceil \log_{3/2}|\mathcal{T}|\rceil$ times, which reduces the size of $\mathcal{S}$ to at most 2. If $\mathcal{S} = \{\tau\}$, we output $t = e^{\tau}$ as the estimate for $\nrm{\vec{x}}$. If $\mathcal{S} = \{\tau,\tau+\ln(2)\}$, we output $t = e^{\tau+\ln(2)/2}$.

To show correctness, we argue that with high probability, at every step of the algorithm there is at least one element of the active set $\mathcal{S}$ that is an additive $\ln(2)/2$-approximation for $\chi$. Hence, in either case ($\mathcal{S} = \{\tau\}$ or $\mathcal{S} = \{\tau, \tau+\ln(2)\}$) the output is a multiplicative $2$-approximation for $\nrm{\vec{x}}$.
Specifically, by Hoeffding's inequality, $\Pr[|\tilde{q} - q_{\rm succ}| \geq 1/12] \leq 2e^{-2k/144}\leq 1/(20\lceil\log_{3/2}(|\mathcal{T}|)\rceil)$, and by the union bound, there is at most 0.05 probability that any of the estimates across all $\lceil\log_{3/2}(|\mathcal{T}|)\rceil$ steps have error more than $1/12$. If $\tau$ is not an additive $\ln(2)/2$ approximation of $\nrm{\vec{x}}$, then by Eq.~\eqref{eq:succ_prob_KP}, $q_{\rm succ}$ lies outside the interval $[10/24, 2/3]$. Thus, in the 0.95 fraction of cases where $|\tilde{q} - q_{\rm succ}| < 1/12$ holds in all steps, the search always correctly decides whether $\tau > \chi$ or $\tau \leq \chi$, unless $\tau$ is an additive $\ln(2)/2$-approximation to $\chi$. However, since we always keep $\tau$ in the set (eliminating only elements that are larger than or smaller than $\tau$), we conclude that, whether or not $\tau$ is an additive $\ln(2)/2$-approximation, the active set $\mathcal{S}$ is guaranteed to retain at least one element that is an additive $\ln(2)/2$-approximation of $\chi$. This proves that the output of the algorithm is a multiplicative $2$-approximation to $\nrm{\vec{x}}$ with high probability.

The overall query complexity is
\begin{align}
Q &= 2k\lceil\log_{3/2}(|\mathcal{T}|)\rceil \lceil \kappa \ln(2/\eta)/2\rceil\\
&=O(\kappa \log\log(\kappa)\log\log\log(\kappa))
\end{align}

More sophisticated algorithms for noisy binary search may be able to eliminate the $\log\log\log(\kappa)$ factor. This large body of work (e.g., \cite{burnashev1974interval,ben-or2008BayesianLearner,wang2022noisySortingcapacity,gretta2023sharpNoisyBinarySearch}) has established that the optimal approach in settings like this one is to maintain a belief distribution over the possible estimates $\tau$, initially uniform. Each step of the algorithm chooses $\tau$ to be the median of the distribution and queries whether $\tau > \chi$. This query returns a noisy answer, and the algorithm responds by updating its belief distribution according to Bayes' rule. This approach may allow us to exploit the additional information we have in our setting, namely, that the probability that KP succeeds follows (up to $O(\eta^2)$ precision) a known functional form, depicted in \autoref{fig:succ_prob}.

\subsection{Achieving linear-in-$\kappa$ complexity}\label{sec:estimate_by_adiabatic}
The methods sketched above do not depend on sophisticated techniques or analytical methods, other than QSVT with filtering polynomials, yet they achieve \textit{nearly} linear-in-$\kappa$ asymptotic scaling, superior to previous known methods for estimating the norm.

We can also combine the observations above with some of the ideas behind adiabatic path-following to achieve \textit{strictly} linear-in-$\kappa$ complexity. Specifically, we propose to estimate the norm of a sequence of linear systems of increasing condition number, where the norm of the solution to the final linear system in the sequence equals $\nrm{\vec{x}}$. The linear systems are related in such a way that the norm cannot change by more than a constant factor from one step to the next. Thus, if we have an estimate of the norm for one linear system, we need only search over a constant-sized interval for the norm of the next linear system---this eliminates the $\mathrm{polylog}(\kappa)$ factors from the norm estimation methods proposed in \autoref{sec:estimate_norm_exhaustive_search} and \autoref{sec:estimate_norm_binary_search} (specifically, the same analysis goes through with $|\mathcal{T}| = O(1)$ rather than $|\mathcal{T}| = O(\log(\kappa))$).

The sequence of linear systems is parameterized by $\sigma \in [\kappa^{-1},1]$ and inspired by the adiabatic path followed by the QLSS in Ref.~\cite{subasi2019QAlgSysLinEqsAdiabatic} and successors.
To define it, let
\begin{equation}
f(\sigma) = \sqrt{\frac{\sigma^2\kappa^2-1}{\kappa^2-1}}\,,
\end{equation}
chosen so that $f(\sigma)^2+ (1-f(\sigma)^2)\kappa^{-2} = \sigma^2$. Observe that $f(\sigma)$ is monotonically increasing for $\sigma \in [\kappa^{-1},1]$ with $f(\kappa^{-1}) = 0$ and $f(1) =1$.
Then, we construct a linear system
\begin{equation}
\bar{A}_\sigma \vec{\bar{x}_\sigma} = \vec{b}\,.
\end{equation}
Here for clarity we interpret $\vec{b}$ as a length-$2^{s}$ vector by padding it with $2^s-m$ zeros. Let $\bar{n}=2^s-n$ and $\bar{m} = 2^s-m$ and define the $2^{s} \times 2^{s+1}$ matrix $\bar{A}_\sigma$ as follows
\NiceMatrixOptions{code-for-first-row = \scriptstyle,code-for-first-col = \scriptstyle }
\begin{equation}\label{eq:barA_sigma}
\bar{A}_\sigma =\;\; \begin{bNiceArray}{cc|cc}[first-row, first-col]
& n                     & \bar{n} & m & \bar{m} \\
m   & \sqrt{1-f(\sigma)^2}A & 0     &  f(\sigma) I_m &  0
\\
\bar{m}   & 0 & 0     &  0 &  0
\end{bNiceArray}
\end{equation}
where the sizes of each block are included for convenience. In essence, $\bar{A}_\sigma$ is really an $m \times (n+m)$ matrix, but the explicit zero padding in Eq.~\eqref{eq:barA_sigma} ensures that the two parts of the matrix separated by the vertical line are each square $2^s \times 2^s$ blocks. This convention makes it more natural to construct a block-encoding for $\bar{A}_\sigma$ on an $(s+1)$-qubit system. In particular, if we further zero-pad $\bar{A}_\sigma$ to be a square $2^{s+1} \times 2^{s+1}$ matrix, we may identify it with the $(s+1)$-qubit operator equivalent to
\begin{equation}
\sqrt{1-f(\sigma)^2}\ketbra{0} \otimes A + f(\sigma) \ketAbraB{0}{1} \otimes I_m
\end{equation}
where $I_m$ is the operator for which $I_m\ket{\vec{e_j}} = \ket{\vec{e_j}}$ if $j < m$ and $I_m\ket{\vec{e_j}} = 0$ otherwise (although the following results would still hold if $I_m$ were replaced with $I_{2^s}$).
Under this identification, we give a block-encoding for $\bar{A}_\sigma$ using one controlled-query to $U_A$ in \autoref{app:block_encodings}. Unlike previous methods \cite{jennings2023QLSS}, we do not use the standard LCU technique to combine the two terms, which would have given a normalization factor $\sqrt{1-f(\sigma)^2} + f(\sigma) >1$ when $\sigma \in (\kappa^{-1},1)$. Note also that here we avoid relying upon the Hermitianized version $\left[\begin{smallmatrix}0 & A \\ A^\dagger & 0\end{smallmatrix}\right]$ of the matrix $A$, as in prior work, which saves a factor of two on the query complexity.

Intuitively, the purpose of $\bar{A}_\sigma$ is that by tuning the value of $\sigma$, we can introduce information about the matrix $A$ and its spectrum gradually: when $\sigma = 1$, $\bar{A}_\sigma$ has no dependence on $A$, and when $\sigma = \kappa^{-1}$, it has full dependence. Crucially, the condition number of $\bar{A}_\sigma$ grows as $\sigma$ decreases; it can be upper bounded by $\sigma^{-1}$ (as justified later). Thus, as $\sigma$ is reduced, we can begin to extract some information about $\nrm{\vec{x}}$ without paying the full $O(\kappa)$ cost associated with the matrix $A$.

We can derive an explicit expression for the solution $\vec{\bar{x}_\sigma}$ to the equation $\bar{A}_\sigma \vec{\bar{x}_\sigma} = \vec{b}$ in terms of the singular value decomposition (SVD) of $A$. Specifically, let $A = \sum_j \varsigma_j \vec{u_j}\vec{v_j}^\dagger$ be a SVD of $A$, with $\varsigma_j \neq 0$ for all $j$, and interpreting $\vec{u_j}$ and $\vec{v_j}$ as length-$2^s$ normalized vectors. Let $\vec{b} = \sum_j w_j\vec{u_j}$ be the decomposition of $\vec{b}$ into left singular vectors of $A$, which is guaranteed to exist since we have assumed that $A\vec{x} = \vec{b}$ has a solution. Define the length-$2^{s+1}$ normalized vector
\begin{equation}
\vec{\bar{v}_{\sigma,j}} = \frac{1}{\sqrt{(1-f(\sigma)^2)\varsigma_j^2 + f(\sigma)^2}}\begin{bmatrix}
\sqrt{1-f(\sigma)^2}\varsigma_j\vec{v_j}\\
f(\sigma) \vec{u_j}
\end{bmatrix}
\end{equation}
Since the sets $\{\vec{u_j}\}$ and $\{\vec{v_j}\}$ are each orthonormal, the set $\{\vec{\bar{v}_{\sigma,j}}\}$ is also orthonormal. In fact, it can be verified that $\{\vec{\bar{v}_{\sigma,j}}\}$ are the right singular vectors of $\bar{A}_\sigma$, and the corresponding left singular vector is $\vec{u_j}$ and correpsonding singular value is $\sqrt{f(\sigma)^2 + (1-f(\sigma)^2)\varsigma_j^2}$.
Thus, by applying the inverted singular values to the decomposition of $\vec{b}$, we may assert that
\begin{equation}\label{eq:barx_sigma}
\vec{\bar{x}_\sigma} = \sum_j \frac{w_j}{\sqrt{f(\sigma)^2+(1-f(\sigma)^2)\varsigma_j^2}} \vec{\bar{v}_{\sigma,j}}\,.
\end{equation}
Matrix-vector block multiplication of $\bar{A}_\sigma \vec{\bar{x}_\sigma}$ yields $\vec{b}$, verifying that $\vec{\bar{x}_\sigma}$ is a solution to the system.  The fact that $\vec{\bar{x}_\sigma}$ is the solution of minimal Euclidean norm follows from the fact that it is orthogonal to the kernel of $\bar{A}_\sigma$ (it is a linear combination of right singular vectors of $\bar{A}_\sigma$ associated with nonzero singular values).

To apply the framework described in this paper to the matrix $\bar{A}_\sigma$, we will need to augment the linear system, as described in \autoref{sec:QLSS_given_norm_main}. In this instance, we augment to form the matrix $\bar{A}_{\sigma,t} = \bar{A}_{\sigma} + t^{-1}\vec{e_m}\vec{e_n}^\dagger$ (cf.~Eq.~\eqref{eq:A_t})
\begin{equation}
\bar{A}_{\sigma,t}= \hspace{-8pt} \begin{bNiceArray}{ccc|cc}[first-row, first-col]
& n                     & 1 & \bar{n}-1 & m & \bar{m} \\
m   & \sqrt{1-f(\sigma)^2}A & 0 & 0     &  f(\sigma) I_m &  0  \\
1   & 0    &  t^{-1} & 0 & 0 & 0 \\
\bar{m}-1& 0 & 0 &     0 & 0& 0
\end{bNiceArray}
\end{equation}
for which we have the linear system $\bar{A}_{\sigma,t}\vec{\bar{x}_{\sigma,t}} = \vec{b'}$. This choice of augmentation avoids the need to expand the Hilbert space and use more than $s+1$ qubits. The relationship between $\vec{\bar{x}_{\sigma, t}}$ and $\vec{\bar{x}}_\sigma$ is the same as the relationship between $\vec{x}_t$ and $\vec{x}$, enabling the methods from prior sections to be directly applied.

Before proceeding, we must establish a few additional properties of the linear system.
\begin{enumerate}
\item All nonzero singular values of $\bar{A}_\sigma$ lie in the interval $[\sigma,1]$.
\item $\nrm{\vec{\bar{x}}_1} = 1$ and $\nrm{\vec{\bar{x}_{1/\kappa}}} = \nrm{\vec{x}}$.
\item For all $\kappa^{-1} \leq \sigma \leq  \sigma'\leq 1$,  it holds that $1 \leq \nrm{\vec{\bar{x}_\sigma}}/\nrm{\vec{\bar{x}_{\sigma'}}} \leq \sigma'/\sigma$.
\end{enumerate}
Property 1 follows from the fact that $\bar{A}_\sigma\bar{A}_\sigma^\dagger= f(\sigma)^2 I_m + (1-f(\sigma)^2)AA^\dagger$ has all nonzero eigenvalues in $[\sigma^2,1]$ by construction.
Property 2 follows by inspection of Eq.~\eqref{eq:barx_sigma}, and the fact that $f(1)=1$ and $f(1/\kappa) = 0$. In particular, we see that $\nrm{\vec{\bar{x}_{1/\kappa}}}^2 = \sum_j |w_j|^2\varsigma_j^{-2} =\nrm{\vec{x}}^2$.
To verify property 3, first note
that due to the monotonicity of $f$ and the fact that $\kappa^{-1} \leq \varsigma_j \leq 1$, we have
\begin{align}
1 &\leq \frac{(f(\sigma')^2+(1-f(\sigma')^2)\varsigma_j^2)^{1/2}}{(f(\sigma)^2+(1-f(\sigma)^2)\varsigma_j^2)^{1/2}} \\
&= \frac{(\sigma'^2 + (1-f(\sigma')^2)(\varsigma_j^2-\kappa^{-2}))^{1/2}}{(\sigma^2 + (1-f(\sigma)^2)(\varsigma_j^2-\kappa^{-2}))^{1/2}} \leq \frac{\sigma'}{\sigma}
\end{align}
for any $\sigma\leq \sigma'$. Thus, working from Eq.~\eqref{eq:barx_sigma}, we have
\begin{align}
\frac{\nrm{\vec{\bar{x}_\sigma}}}{\nrm{\vec{\bar{x}_{\sigma'}}}} &= \frac{\sqrt{\sum_j |w_j|^2 (f(\sigma)^2+(1-f(\sigma)^2)\varsigma_j^2)^{-1}}}{\sqrt{\sum_j |w_j|^2 (f(\sigma')^2+(1-f(\sigma')^2)\varsigma_j^2)^{-1}}} \nonumber \\
&\leq \frac{\sqrt{\sum_j |w_j|^2 (f(\sigma)^2+(1-f(\sigma)^2)\varsigma_j^2)^{-1}}}{\sqrt{\sum_j |w_j|^2\frac{\sigma^2}{\sigma'^2} (f(\sigma)^2+(1-f(\sigma)^2)\varsigma_j^2)^{-1}}} \nonumber\\
&= \frac{\sigma'}{\sigma}
\end{align}

Now we are ready to describe the algorithm. We propose to learn $\nrm{\vec{x}} = \nrm{\vec{\bar{x}_{1/\kappa}}}$ by sequentially estimating the norm of $\nrm{\vec{\bar{x}_{2^{-j}}}}$ for $j=0,1,\ldots,\log_2(\kappa)$ (for simplicity, here we round $\kappa$ up to the closest exact power of 2). For $j=0$, we use the estimate $t_0 = 1$, which is exact, by property 2 above. We then aim to generate estimates $t_1,t_2,\ldots, t_{\log_2(\kappa)}$ such that each $t_j$ is a multiplicative $2$-approximation of $\nrm{\vec{\bar{x}_{2^{-j}}}}$.

The key insight is that, from property 3, if $t_{j-1}$ is a valid 2-approximation, i.e.~$\nrm{\vec{\bar{x}_{2^{-j+1}}}} \in [t_{j-1}/2,2t_{j-1}]$, then it must hold that $\nrm{\vec{\bar{x}_{2^{-j}}}} \in [t_{j-1}/2,4t_{j-1}]$. We can find a 2-approximation $t_j$ to
$\nrm{\vec{\bar{x}_{2^{-j}}}}$ by exhaustively (or binarily) searching $O(1)$ candidates in this interval---that is, whereas the analysis in prior subsections required the size of the set $\mathcal{T}$ of candidates to grow as $O(\log(\kappa))$ (see Eq.~\eqref{eq:T_candidates}), here we have $|\mathcal{T}| = 1$ instead.
Furthermore, the cost of running KR or KP for a particular candidate is reduced due to the fact that the condition number of $\bar{A}_{2^{-j}}$ is only $2^{j}$, as seen in property 1.

Ultimately, from Eq.~\eqref{eq:Q_exhaustive_nonoptimized}, the expected query complexity of producing the estimate $t_j$ using the exhaustive search method is $O(2^j|\mathcal{T}| \log(|\mathcal{T}|)) = O(2^j)$, and the probability that $t_j$ is not a valid $2$-approximation---conditioned on $t_{j-1}$ being a valid 2-approximation---is at most $0.05$. To suppress this conditional failure probability from $0.05$ to $\delta$, we perform median amplification \cite[Lemma 1]{nagaj2009FastAmpQMA} at multiplicative overhead $O(\log(1/\delta))$ to the query complexity. Naively, we might choose $\delta=O(1/\log(\kappa))$ so that there is high probability that all $\log_2(\kappa)$ steps succeed; however, if we do so then the final step, for which the condition number is $\kappa$, will have complexity $O(\kappa \log(1/\delta)) = O(\kappa \log\log(\kappa))$ complexity.

Instead, we employ a version of the ``log log trick'' \cite{kothari2023meanEstimationSourceCode}, choosing $\delta$ to be smaller when $j$ is smaller---we can afford to do more median amplification at the beginning of the sequence because the condition number is smaller and the norm estimation is cheaper. Specifically, we use median amplification to suppress the failure probability of step $j$ to $e^{-\Omega(1+\log_2(\kappa)-j)}$, at multiplicative overhead $O(1+\log_2(\kappa)-j)$, and we conclude that the overall expected query cost of step $j$ is $O( 2^{j}(1+\log_2(\kappa)-j))$. By the union bound, the probability that at least one of the steps fails to generate a $2$-approximation is upper bounded by a geometrically decaying series $\sum_{j=1}^{\log_2(\kappa)} e^{-\Omega(1+\log_2(\kappa)-j)}$, which is at most a small constant. Thus, with high probability all of the steps succeed, and the output is a multiplicative 2-approximation for $\nrm{\vec{x_{1/\kappa}}} = \nrm{\vec{x}}$.

The overall total query complexity is upper bounded by the sum of the query complexity of the $\log_2(\kappa)$ steps, given by
\begin{align}
Q&=\sum_{j=1}^{\log_2(\kappa)} O(2^j(1+\log_2(\kappa)-j)) \\
&\leq  O(\kappa) \sum_{j'=0}^{\infty } 2^{-j'}(1+j')
\leq O(\kappa)
\end{align}
where we have substituted $j' = \log_2(\kappa)-j$ and upper bounded the finite sum by its infinite extension.

In summary, the method solves the norm estimation problem up to a constant factor with optimal $O(\kappa)$ query complexity. It does so by leveraging an idea that is inspired by adiabatic path-following; in fact, it follows essentially the same family of linear systems as prior adiabatic solvers. However, the analysis is fairly simple, and crucially it avoids the need for rigorous analysis of the adiabatic theorem.

By first estimating the norm with this method and then running \autoref{algo:main_algo} to produce $\ket{\vec{\tilde{x}}}$, we obtain a method for solving the QLSP with overall query complexity $O(\kappa\log(1/\varepsilon))$. In \autoref{app:explicit_optimal_QLSS} of the appendix, we give a more detailed specification of an optimal QLSS with $O(\kappa\log(1/\varepsilon))$ complexity, which follows the same general approach sketched above, and we analyze its complexity, including constant prefactors, in \autoref{thm:optimal_QLSS}.

\subsection{Improving the approximation ratio }\label{sec:improving_approx_ratio}
We have now seen several methods for obtaining a constant-factor approximation to the norm $\nrm{\vec{x}}$. However, in many instances we may wish to improve the approximation ratio of our estimate. For one, the success probability of \autoref{algo:main_algo} increases (approaching 1) as the accuracy of the norm estimate improves, motivating us to seek the best possible estimate. Additionally, some applications require not only access to the normalized state $\ket{\vec{x}}$, but also a precise estimate for $\nrm{\vec{x}}$ that is correct up to small relative error---see \autoref{sec:conclusion}.

Given a multiplicative 2-approximation $t \in [\nrm{\vec{x}}/2, 2\nrm{\vec{x}}]$, one can improve the estimate to a multiplicative $(1+\varepsilon)$-approximation
\begin{equation}
t_{\rm out} \in [(1+\varepsilon)^{-1}\nrm{\vec{x}}, (1+\varepsilon)\nrm{\vec{x}}]
\end{equation}
using amplitude estimation \cite{brassard2002AmpAndEst} (the method is easily generalized to handle input approximations with constant-factors worse than 2), as we now explain. Amplitude estimation allows one to estimate the quantity $\nrm{\Pi \ket{\psi}}^2$ to additive precision $\nu$, using $O(1/\nu)$ calls to a procedure for preparing $\ket{\psi}$ and the ability to recognize when a state is in the image of a projector $\Pi$ \cite{brassard2002AmpAndEst}.
Let $\eta = \sqrt{\varepsilon/100}$ and, as in \autoref{sec:estimate_norm_binary_search}, consider the procedure that prepares $\ket{\vec{e_n}}$ and applies KP for the matrix $G_t$. The success probability $q$ of this procedure can be cast as a measurable quantity $\nrm{\Pi \ket{\psi}}^2$, and by Eq.~\eqref{eq:succ_prob_KP}, it lies within $\eta^2 = \varepsilon/100$ of the quantity
\begin{equation}
q_t = \cos^2(\theta_t) =  t^2/(t^2+\nrm{\vec{x}}^2) \in [0.2,0.8]\,.
\end{equation}
Using $O(1/\varepsilon)$ queries to this KP procedure, amplitude estimation can produce an estimate $\tilde{q}$ for $q$ that is correct up to additive  error $\varepsilon/100$, with probability 0.95. In this 0.95 fraction of cases, by the triangle inequality, we have $|\tilde{q}-q_t| \leq \varepsilon/50$. Furthermore, defining the relative error as $\Delta = \tilde{q}/q_t - 1$, we have $|\Delta| \leq \varepsilon/10$.  Then, to produce an estimate for $\nrm{\vec{x}}$, one can take the result $\tilde{q}$ of amplitude estimation and output the quantity
\begin{align}
t_{\rm out} &= \frac{t\sqrt{1-\tilde{q}}}{\sqrt{\tilde{q}}} = \frac{t\sqrt{1-q_t(1+\Delta)}}{\sqrt{q_t(1+\Delta)}} \nonumber \\
&= \frac{t\sqrt{\frac{\nrm{\vec{x}}^2}{t^2}-\Delta}}{\sqrt{1+\Delta}}
= \nrm{\vec{x}}\frac{\sqrt{1-\frac{t^2\Delta}{\nrm{\vec{x}}^2}}}{\sqrt{1+\Delta}}\,.
\end{align}
Since $t^2/\nrm{\vec{x}}^2 \leq 4$ and $|\Delta| \leq \varepsilon/10$, the output is guaranteed to be multiplicative $(1+\varepsilon)$-approximation for $\nrm{\vec{x}}$.
Accounting for $O(1/\varepsilon)$ calls to KP, each costing $O(\kappa\log(1/\eta))$, the total complexity is $O(\kappa\log(1/\varepsilon)/\varepsilon)$.

Since the query complexity of obtaining the $2$-approximation in the first place is $O(\kappa)$ using the method from \autoref{sec:estimate_by_adiabatic}, we have thus established that the total query complexity to obtain a multiplicative $(1+\varepsilon)$-approximation of $\nrm{\vec{x}}$ is
\begin{equation}
Q = O(\kappa\log(1/\varepsilon)/\varepsilon)
\end{equation}
In \autoref{thm:norm_query_lower_bound} of \autoref{app:norm_query_lower_bound}, building on the method of Ref.~\cite{Orsucci2021solvingclassesof}, we derive a lower bound on the query complexity of this task when $\varepsilon < 1/4$ of
\begin{equation}
Q = \Omega(\min(\kappa/\varepsilon,N))\,,
\end{equation}
where $N$ is the size of the matrix $A$. Thus, we have established optimal-in-$\kappa$ query complexity for norm estimation, and our $\varepsilon$ dependence is off by a single logarithmic factor. It is an interesting question for future work to tighten the $\varepsilon$ dependence of the complexity of norm estimation.

\section{Constant prefactor analysis}\label{sec:constant_factors}

\begin{table*}[t]
\centering
\begin{adjustbox}{max width=\textwidth}

\begin{tabular}{|c|c|c|c|c|}
\hline
& \textbf{QLSS method} & \makecell{\textbf{Asymptotic complexity} \\ $ + \;O(\kappa \log(1/\varepsilon)) $} & \makecell{\textbf{Explicit upper bound} \\ $(\kappa \in [3,10^6])$} & \makecell{\textbf{Value at} \\ $(\kappa,\varepsilon) =(10^5,10^{-10})$} \\
\hline
\hline
\multirow{2}{*}{\rotatebox[origin=c]{90}{prior}} & Quantum walk method \cite{costa2021OptimalLinearSystem} & $O(\kappa)$ & $234470\kappa + 4\kappa \ln(2/\varepsilon)$ & $234562\kappa$\\
\cline{2-5}
& Randomization method \cite{subasi2019QAlgSysLinEqsAdiabatic} & $O(\kappa\log(\kappa))$ & $162\kappa\ln(\kappa) + 188\kappa + 5.2\kappa\ln(1/\varepsilon)$ \cite{jennings2023QLSS} & $2173\kappa$ \\
\hline
\hline
\multirow{4}{*}{\rotatebox[origin=c]{90}{\makebox[2mm][c]{this work \;\;\;}}} & \makecell{Augmented linear system KR \\ with exhaustive norm search } & $O(\kappa \log(\kappa)\log\log(\kappa))$ & $6 \kappa \ln(\kappa) +6\kappa + 1.1\kappa\ln(1/\varepsilon)$ & $83\kappa$\\
\cline{2-5}
& \makecell{Augmented linear system KR \\ with Grover norm search} & $O(\kappa \sqrt{\log(\kappa)}\log\log(\kappa))$ & $10 \kappa \sqrt{\ln(\kappa)+1} +12\kappa + 1.1\kappa\ln(1/\varepsilon)$ & $66\kappa$\\
\cline{2-5}
& \makecell{Augmented linear system KR \\ with binary norm search } & $O(\kappa\log\log(\kappa)\log\log\log(\kappa))$ & \text{not analyzed} & not analyzed \\
\cline{2-5}
& \makecell{Augmented linear system KR \\ with adiabatic norm search } & $O(\kappa)$ & $56\kappa + 1.05\kappa\log(1/\varepsilon)$ & $80\kappa$ \\
\hline
\end{tabular}
\end{adjustbox}
\caption{A comparison of our proposed QLSS methods with previous optimal and near-optimal methods for which explicit query complexity bounds have been derived. The explicit upper bounds omit subleading terms, and the rows for Grover and exhaustive search replace doubly and triply logarithmic factors with their maximum values on the domain $\kappa \in [3,10^6]$ for compactness---see \autoref{app:explicit_near_optimal_QLSS} for more detailed expressions. In all cases, the evaluation of the bound at $\kappa=10^5$ and $\varepsilon =10^{-10}$ is calculated using the exact expression. For the quantum walk method, a numerical calculation of the bound on the domain $\kappa \in [1,50]$ suggested the bound is about 20 times smaller, but here we report the fully rigorous bound \cite{costa2021OptimalLinearSystem}. Additionally, the estimates for the  quantum walk and randomization method include an additional factor of 2 compared to the numerical values reported elsewhere (e.g., in Refs.~\cite{costa2021OptimalLinearSystem, jennings2023QLSS}) because when $A$ is non-Hermitian they require two queries to $U_A$ to block-encode the Hermitianized $\left[\begin{smallmatrix} 0 & A \\ A^\dagger & 0 \end{smallmatrix}\right]$. We expect the practical performance of all of  these methods to be significantly better than their bounds. }\label{tab:comparison}
\end{table*}

The constant prefactors and explicit complexity expressions for the QLSS are important for determining whether applications based on the QLSS are viable.
We derived the asymptotic complexities of several distinct norm estimation methods in \autoref{sec:estimating_the_norm}; the ability to estimate the norm up to a constant multiplicative factor implies a full-fledged QLSS at the cost of $O(\kappa\log(1/\varepsilon))$ additional complexity.  However, the implementations and proofs provided for these algorithms were optimized for simplicity and ease of presentation, rather than for their constant prefactors. In \autoref{app:explicit_near_optimal_QLSS} of the appendix, we provide detailed analyses of two QLSS methods, one that uses a variant of the exhaustive search method for learning the norm, and one that additionally applies amplitude amplification. We arrive at explicit complexity expressions in \autoref{thm:QLSS_random_t} and \autoref{thm:QLSS_random_t_FPAA}. In deriving these methods, we have put a bit more thought into reducing the constant factors, although there remains room for improvement. For example, in \autoref{algo:random_t_full_QLSS} (analyzed in \autoref{thm:QLSS_random_t}), rather than exhaustively searching over a discrete set of candidate estimates $\tau = \ln(t)$ for the norm $\nrm{\vec{x}}$, we opt to choose $\tau$ (nearly) uniformly at random from the continuum, repeating this process until we find a $t$ for which \autoref{algo:main_algo} succeeds. We do not need to spend queries repeating \autoref{algo:main_algo} many times to become confident in this value of $t$, and we need not re-run KR using the value of $t$ we find; we can proceed directly to the KP step that refines the state to error $\varepsilon$ to solve the QLSP. Ultimately, we achieve complexity that scales as $O(\kappa\log(\kappa)\log\log(\kappa))$, but this is upper bounded by the easier-to-use expression reported in \autoref{tab:comparison} and Eq.~\eqref{eq:Q_exhaustive_search_practical} when $\kappa \in [3,10^6]$, which covers the vast majority of practical cases. See Eq.~\eqref{eq:Q_FPAA_practical} for the analogous expression for the amplitude-amplified method.

In \autoref{app:explicit_optimal_QLSS}, we give a detailed analysis of an optimal QLSS (\autoref{algo:full_QLSS_constant_prefactors}). which resembles the QLSS described in \autoref{sec:estimate_by_adiabatic} and also has optimal $O(\kappa\log(1/\varepsilon))$ complexity. One difference is that with each step in the sequence, \autoref{algo:full_QLSS_constant_prefactors} increases the condition number of the linear system by a factor of about 20, rather than a factor of 2. Furthermore, rather than learning a multiplicative 2-approximation of the norm at each step, it targets an approximation ratio that begins large and gradually decreases with each step. The decreasing approximation ratio plays the role of median amplification and represents a different manifestation of the log log trick. Some aspects of the analysis are fairly tedious (perhaps reflecting the fact that this method is more complicated than the others considered), but crucially there is no need for the adiabatic theorem. Ultimately, we prove in \autoref{thm:optimal_QLSS} that the method achieves expected complexity upper bounded by
\begin{equation}
Q \leq 56.0 \kappa + 1.05 \kappa \ln(\frac{\sqrt{1-\varepsilon^2}}{\varepsilon})  + 2.78 \ln(\kappa)^3 + 3.17\,,
\end{equation}
which holds for any $\kappa$ and $\varepsilon$.

\autoref{tab:comparison} compares these complexity statements to the rigorous bounds provided for the quantum walk method \cite{costa2021OptimalLinearSystem} and the randomization method \cite{subasi2019QAlgSysLinEqsAdiabatic}. We see that all of our methods yield considerable savings of more than an order of magnitude. The rigorous guarantee provided by the asymptotically near-optimal method using ``Grover norm search'' is actually better than the asymptotically optimal ``adiabatic norm search'' method for $\kappa \approx 10^6$. Indeed, it is quite possible that an asymptotically suboptimal method could ultimately be the the best option practically, since factors like $\sqrt{\ln(\kappa)}\ln\ln(\kappa)$ evaluate to less than 10 at the scale of $\kappa =10^6$, and grow extremely slowly in $\kappa$.

We believe the rigorous bounds we report could be improved with more work. However, some aspects of the analysis will always be loose; for example, we see no way around using worst case error bounds on the QSVT polynomials used to do KP and KR. We expect that the empirical performance of our algorithms will have lower constant factors than those we have reported. Indeed, numerical experiments conducted in Ref.~\cite{costa2023discreteConstantFactors} suggest the actual constant prefactors of both the randomization method and the quantum walk method are significantly smaller than their rigorous bounds, and that the quantum walk method is better than the randomization method in practice. Concretely, experiments on $16 \times 16$ random matrices of increasing condition number (up to $\kappa = 50$) suggest that for those instances the quantum walk method can prepare an ansatz state $\ket{\vec{x_{\rm ans}}}$ with constant overlap $\gamma \approx 0.98$ in complexity roughly $15\kappa$ (here accounting for the factor of 2 to Hermitianize the matrix, see caption of \autoref{tab:comparison}), yielding overall QLSS complexity roughly $17\kappa + 2.1\kappa \ln(1/\varepsilon)$.  However, the numerical simulations were on a specific random ensemble of small matrices (no larger than $16 \times 16$), and it remains untested if this performance would be matched for larger instances, and for instances appearing in actual applications. Empirical analyses are valuable, but it is difficult to replace a broad worst-case guarantee. The question of which approach yields the best practical performance on application-relevant instances remains an interesting open problem.

\section{Conclusions and summary}\label{sec:conclusion}

Here we have developed a new framework for the QLSP, one where the Euclidean norm $\nrm{\vec{x}}$ plays a central role. We have shown that if the value of $\nrm{\vec{x}}$ is known up to a constant factor, the QLSP is simple to solve in optimal complexity; the only algorithmic tools required are well-established QSVT-based methods for reflecting about the kernel of an operator.

Conceptually, then, an important aspect of our QLSS is that it requires the ability to first estimate $\nrm{\vec{x}}$, a single real number in the interval $[1,\kappa]$. Norm estimation replaces the cost-intensive and technically challenging task of preparing a high-overlap $n$-dimensional ansatz state, which has been the strategy in prior work.
One reason to prefer norm estimation over ansatz-state preparation is that the norm need only be learned once, whereas ansatz states may need to be re-prepared each time the linear system needs to be solved. Another reason is that in certain cases we may have information about the norm that assists us to obtain a constant-factor approximation; for example, if the norm concentrates for a certain class of instances, the ensemble average may act as a decent guess for the norm for typical instances, or at least it can act as a starting point that enables a faster search.

Having established the importance of norm estimation for solving the QLSP, we have initiated a systematic study of methods for accomplishing this task. We have proved a lower bound of $\Omega(\kappa \varepsilon^{-1})$ query compleixty to estimate the norm to within a factor of $1+\varepsilon$, and we have given several methods that nearly achieve this bound. For one, any constant factor approximation can be improved to a $1+\varepsilon$ approximation at cost $O(\kappa\varepsilon^{-1}\log(1/\varepsilon))$; matching the lower bound to within a $\log(1/\varepsilon)$ factor. To obtain the initial constant-factor approximation,  our simple framework offers a straightforward method that is nearly optimal---its $\kappa$ dependence is off by a doubly logarithmic factor of $O(\log\log(\kappa)\log\log\log(\kappa))$. Additionally, we have shown that this factor can be eliminated, yielding a norm estimation algorithm with optimal $O(\kappa)$ complexity, by combining our framework with ideas from the adiabatic path-following methods employed in prior work for ansatz preparation. Here, the relative simplicity of the norm estimation problem keeps the analysis manageable and avoids the need to analyze the adiabatic theorem. Our final complexity of $O(\kappa\log(1/\varepsilon)/\varepsilon)$ shaves off several logarithmic factors in $\kappa$ and $1/\varepsilon$ from the complexity of the best norm-estimation method known previously \cite{chakraborty2018BlockMatrixPowers}.

Furthermore, estimating the norm is an important task in its own right, independent of how it is used within our QLSS. By improving the state of the art for norm estimation, we reduce the asymptotic complexity for several end-to-end applications \cite{dalzell2023quantumAlgorithmsSurvey}. For example, knowing the norm is essential when the computational task being solved is to estimate an inner product $W = \vec{w}^\dagger \vec{x}$, where $\vec{w}$ is a fixed vector and $\vec{x}$ is the solution to a linear system. This can be solved by rewriting $W$ as $\nrm{\vec{w}}\nrm{\vec{x}}\braket{\vec{w}}{\vec{x}}$: we may use a QLSS to prepare $\ket{\vec{x}}$ and then apply overlap estimation \cite{knill2007ObservableMeasurement} to estimate $\braket{\vec{w}}{\vec{x}}$, but notably we still need to know $\nrm{\vec{x}}$ to compute the output $W$. This situation is the prototypical problem solved by quantum algorithms for differential equations \cite{berry2014highOrderQuantumAlgorithmDiffEQ,montanaro2016quantum}, where $A\vec{x} =\vec{b}$ is a discretization of the differential equation and $W$ is some physical quantity, such as an electromagnetic scattering cross section \cite{clader2013preconditioned}. A similar situation arises for quantum algorithms for certain problems in machine learning, such as Gaussian process regression \cite{zhao2015QAssisstedGaussProcRegr, zhao2019TrainingGaussianProcess} and support vector machines \cite{rebentrost2014QSVM}.

Although the existence of QLSSs with asymptotically optimal $O(\kappa \log(1/\varepsilon))$ query complexity has been previously established in Ref.~\cite{costa2021OptimalLinearSystem}, our approach matches their complexity using a distinct approach with a (we believe) simpler analysis, and offers the potential for better rigorous performance guarantees. Indeed, we have given explicit complexity statements for our methods that are significantly better than those available previously, although we expect that all of these methods under consideration have substantial room for further optimization.
Moreover, our framework is also slightly more flexible than much of the previous work on QLSSs. We do not require any assumptions on our linear system $A\vec{x}=\vec{b}$, other than that it has at least one solution. In contrast, prior work often assumes $A$ is invertible, and some prior work, such as Refs.~\cite{lin2019OptimalQEigenstateFiltering,costa2021OptimalLinearSystem}, handles non-Hermitian matrices $A$ indirectly by doubling the dimension, and examining the Hermitian matrix $\left[\begin{smallmatrix}0 & A \\
A^\dagger & 0 \end{smallmatrix}\right]$ instead. In general,  this incurs a factor of 2 in the query complexity to $U_A$ and $U_A^\dagger$.

On the other hand, our framework is not able to handle the situation where there is no $\vec{x}$ satisfying $A\vec{x}=\vec{b}$, and one instead seeks to find the least-squares solution that minimizes $\nrm{A\vec{x}-\vec{b}}$. This task is handled by the QLSS based on variable-time amplitude amplification of Ref.~\cite{chakraborty2018BlockMatrixPowers}, and fitting it into our framework is an interesting open problem.

\subsection*{Acknowledgments}

We thank Fernando Brandao and Grant Salton for discussions, and Mario Berta and Sam McArdle for extensive comments on a draft of this paper.  Special thanks to Andr\'as Gily\'en for the suggestion to generalize eigenstate filtering to kernel projection and use $Q_{\vec{b}}A$ directly, rather than its doubled Hermitianized version. We are grateful to the AWS Center for Quantum Computing for its support.

\balance
% $ biblatex auxiliary file $
% $ biblatex bbl format version 3.2 $
% Do not modify the above lines!
% This is an auxiliary file used by the 'biblatex' package.
% This file may safely be deleted. It will be recreated by
% biber as required.
\begingroup
\makeatletter
\<EMAIL_ADDRESS>{Missing 'biblatex' package}
{The bibliography requires the 'biblatex' package.}
\aftergroup\endinput}
\endgroup

\preamble{%
\newcommand{\lName}{0}%
\newcommand{\arxiv}[1]{arXiv:\href{https://arxiv.org/abs/#1}{\ttfamily{#1}}\removefirstdot}%
\newcommand{\arXiv}[1]{arXiv:\href{https://arxiv.org/abs/#1}{\ttfamily{#1}}\removefirstdot}%
\newcommand{\iacr}[1]{ePrint:\href{https://eprint.iacr.org/#1}{\ttfamily{#1}}\removefirstdot}%
\def\removefirstdot#1{\if.#1{}\else#1\fi}%
\providecommand{\multiletter}[1]{#1}\renewcommand{\multiletter}[1]{#1}%
\DeclareRobustCommand{\dutchPrefix}[2]{#2}%
\providecommand{\dutchPrefix}[2]{#2}\renewcommand{\dutchPrefix}[2]{#2}%
\newcommand{\skp}[3]{#2}%
\newcommand{\focs }[1]{\if\lName1\skp{ }{Proceedings of the #1 {IEEE} Symposium on Foundations of Computer Science ({FOCS})}{ }\else{FOCS}\fi}%
\newcommand{\stoc }[1]{\if\lName1\skp{ }{Proceedings of the #1 {ACM} Symposium on the Theory of Computing ({STOC})}{ }\else{STOC}\fi}%
\newcommand{\soda }[1]{\if\lName1\skp{ }{Proceedings of the #1 {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})}{ }\else{SODA}\fi}%
\newcommand{\stacs }[1]{\if\lName1\skp{ }{Proceedings of the #1 Symposium on Theoretical Aspects of Computer Science ({STACS})}{ }\else{STACS}\fi}%
\newcommand{\itcs }[1]{\if\lName1\skp{ }{Proceedings of the #1 Innovations in Theoretical Computer Science Conference ({ITCS})}{ }\else{ITCS}\fi}%
\newcommand{\fsttcs }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Conference on Foundations of Software Technology and Theoretical Computer Science ({FSTTCS})}{ }\else{FSTTCS}\fi}%
\newcommand{\mfcs }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Symposium on Mathematical Foundations of Computer Science ({MFCS})}{ }\else{MFCS}\fi}%
\newcommand{\ccc }[1]{\if\lName1\skp{ }{Proceedings of the #1 {IEEE} Conference on Computational Complexity ({CCC})}{ }\else{CCC}\fi}%
\newcommand{\isit }[1]{\if\lName1\skp{ }{Proceedings of the #1 {IEEE} International Symposium on Information Theory ({ISIT})}{ }\else{ISIT}\fi}%
\newcommand{\colt }[1]{\if\lName1\skp{ }{Proceedings of the #1 Conference On Learning Theory ({COLT})}{ }\else{COLT}\fi}%
\newcommand{\nips }[1]{\if\lName1\skp{ }{Advances in Neural Information Processing Systems #1 ({NIPS})}{ }\else{NIPS}\fi}%
\newcommand{\aistats }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Conference on Artificial Intelligence and Statistics ({AISTATS})}{ }\else{AISTATS}\fi}%
\newcommand{\icml }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Conference on Machine Learning ({ICML})}{ }\else{ICML}\fi}%
\newcommand{\icalp }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Colloquium on Automata, Languages, and Programming ({ICALP})}{ }\else{ICALP}\fi}%
\newcommand{\esa }[1]{\if\lName1\skp{ }{Proceedings of the #1 Annual European Symposium on Algorithms ({ESA})}{ }\else{ESA}\fi}%
\newcommand{\tqc }[1]{\if\lName1\skp{ }{Proceedings of the #1 Conference on the Theory of Quantum Computation, Communication, and Cryptography ({TQC})}{}\else{TQC}\fi}%
\newcommand{\isca }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Symposium on Computer Architecture ({ISCA})}{}\else{ISCA}\fi}%
\newcommand{\isaac }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Symposium on Algorithms and Computation ({ISAAC})}{ }\else{ISAAC}\fi}%
\newcommand{\aaai }[1]{\if\lName1\skp{ }{Proceedings of the #1 AAAI Conference on Artificial Intelligence}{ }\else{AAAI}\fi}%
\newcommand{\socg }[1]{\if\lName1\skp{ }{Proceedings of the #1 Annual Symposium on Computational geometry}{ }\else{SoCG}\fi}%
\newcommand{\sofsem }[1]{\if\lName1\skp{ }{SOFSEM #1: Theory and Practice of Computer Science}{ }\else{SOFSEM}\fi}%
\newcommand{\ecc }[1]{\if\lName1\skp{ }{#1 European Control Conference (ECC)}{ }\else{ECC}\fi}%
\newcommand{\crypto }[1]{\if\lName1\skp{ }{Advances in Cryptology -- CRYPTO #1}{ }\else{CRYPTO}\fi}%
\newcommand{\asiacrypt }[1]{\if\lName1\skp{ }{Advances in Cryptology -- ASIACRYPT #1}{ }\else{ASIACRYPT}\fi}%
\newcommand{\eurocrypt }[1]{\if\lName1\skp{ }{Advances in Cryptology -- EUROCRYPT #1}{ }\else{EUROCRYPT}\fi}%
\newcommand{\pqcrypto }[1]{\if\lName1\skp{ }{Post-Quantum Cryptography}{ }\else{PQCrypto}\fi}%
\newcommand{\scConference}[1]{\if\lName1\skp{ }{Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis}{ }\else{SC}\fi}%
\newcommand{\fccm}[1]{\if\lName1\skp{ }{#1 {IEEE} Annual International Symposium on Field-Programmable Custom Computing Machines}{ }\else{FCCM}\fi}%
\newcommand{\lattice }[1]{\if\lName1\skp{ }{Proceedings of the #1 International Symposium on Lattice Field Theory}{ }\else{Lattice}\fi}%
\newcommand{\aft }[1]{\if\lName1\skp{ }{Proceedings of the #1 ACM Conference on Advances in Financial Technologies}{ }\else{AFT}\fi}%
\newcommand{\secConference }[1]{\if\lName1\skp{ }{Proceedings of the IEEE/ACM #1 Symposium on Edge Computing}{ }\else{SEC}\fi}%
\newcommand{\ims }[1]{\if\lName1\skp{ }{#1 {IEEE} {MTT}-{S} International Microwave Symposium (IMS)}{ }\else{IMS}\fi}%
\newcommand{\jacm }{\if\lName1\skp{ }{Journal of the ACM}{ }\else{J. ACM}\fi}%
\newcommand{\acmta }{\if\lName1\skp{ }{ACM Transactions on Algorithms}{ }\else{{ACM} Trans. Algorithms}\fi}%
\newcommand{\acmtct }{\if\lName1\skp{ }{ACM Transactions on Computation Theory}{ }\else{ACM Trans. Comput. Theory}\fi}%
\newcommand{\acmtqc }{\if\lName1\skp{ }{ACM Transactions on Quantum Computing}{ }\else{ACM Trans. Quantum Comput.}\fi}%
\newcommand{\acmjetcs }{\if\lName1\skp{ }{ ACM Journal on Emerging Technologies in Computing Systems }{ }\else{ACM J. Emerg. Technol. Comput. Syst.}\fi}%
\newcommand{\canadianjmath }{\if\lName1\skp{ }{Canadian Journal of Mathematics }{ }\else{Can. J. Math.}\fi}%
\newcommand{\jams }{\if\lName1\skp{ }{Journal of the AMS}{ }\else{J. AMS}\fi}%
\newcommand{\bullAMS }{\if\lName1\skp{ }{Bulletin of the American Mathematical Society}{ }\else{Bull. AMS}\fi}%
\newcommand{\pams }{\if\lName1\skp{ }{Proceedings of the AMS}{ }\else{Proc. AMS}\fi}%
\newcommand{\linalgappl }{\if\lName1\skp{ }{Linear Algebra and its Applications}{ }\else{Linear Algebra App.}\fi}%
\newcommand{\jalgo }{\if\lName1\skp{ }{Journal of Algorithms}{ }\else{J. Algorithms}\fi}%
\newcommand{\jcss }{\if\lName1\skp{ }{Journal of Computer and System Sciences}{ }\else{J. Comput. Syst. Sci.}\fi}%
\newcommand{\jcomputapplmath}{\if\lName1\skp{ }{Journal of Computational and Applied Mathematics}{ }\else{J. Comput. Appl. Math.}\fi}%
\newcommand{\cc }{\if\lName1\skp{ }{Computational Complexity}{ }\else{Comput. Complex.}\fi}%
\newcommand{\algor }{\if\lName1\skp{ }{Algorithmica}{ }\else{Algorithmica}\fi}%
\newcommand{\comb }{\if\lName1\skp{ }{Combinatorica}{ }\else{Combinatorica}\fi}%
\newcommand{\cacm }{\if\lName1\skp{ }{Communications of the ACM}{ }\else{Commun. ACM}\fi}%
\newcommand{\sigart }{\if\lName1\skp{ }{SIGART Bulletin}{ }\else{SIGART Bull.}\fi}%
\newcommand{\sigactn }{\if\lName1\skp{ }{SIGACT News}{ }\else{SIGACT News}\fi}%
\newcommand{\eatcsbul }{\if\lName1\skp{ }{Bulletin of the {EATCS}}{ }\else{Bull. {EATCS}}\fi}%
\newcommand{\siamrev }{\if\lName1\skp{ }{SIAM Review}{ }\else{SIAM Rev.}\fi}%
\newcommand{\siamjc }{\if\lName1\skp{ }{SIAM Journal on Computing}{ }\else{SIAM J. Comp.}\fi}%
\newcommand{\siamjo }{\if\lName1\skp{ }{SIAM Journal on Optimization}{ }\else{SIAM J. Opt.}\fi}%
\newcommand{\siamjdm }{\if\lName1\skp{ }{SIAM Journal on Discrete Mathematics}{ }\else{SIAM J. Disc. Math.}\fi}%
\newcommand{\siamjnum }{\if\lName1\skp{ }{SIAM Journal on Numerical Analysis}{ }\else{SIAM J. Num. Anal.}\fi}%
\newcommand{\siamjmathanal }{\if\lName1\skp{ }{SIAM Journal on Mathematical Analysis}{ }\else{SIAM J. Math. Anal.}\fi}%
\newcommand{\discmath }{\if\lName1\skp{ }{Discrete Mathematics}{ }\else{Disc. Math.}\fi}%
\newcommand{\das }{\if\lName1\skp{ }{Discrete Applied Mathematics}{ }\else{Disc. App. Math.}\fi}%
\newcommand{\annmath }{\if\lName1\skp{ }{Annals of Mathematics}{ }\else{Ann. Math.}\fi}%
\newcommand{\amatstat }{\if\lName1\skp{ }{Annals of Mathematical Statistics}{ }\else{Ann. Math. Stat.}\fi}%
\newcommand{\rms }{\if\lName1\skp{ }{Russian Mathematical Surveys}{ }\else{Russ. Math. Surv.}\fi}%
\newcommand{\invmath }{\if\lName1\skp{ }{Inventiones Mathematicae}{ }\else{Inv. Math.}\fi}%
\newcommand{\jnumber }{\if\lName1\skp{ }{Journal of Number Theory}{ }\else{J. Num. Th.}\fi}%
\newcommand{\tcs }{\if\lName1\skp{ }{Theoretical Computer Science}{ }\else{Theor. Comput. Sci.}\fi}%
\newcommand{\numeralgorithms}{\if\lName1\skp{ }{Numerical Algorithms}{ }\else{Numer. Algorithms}\fi}%
\newcommand{\toc }{\if\lName1\skp{ }{Theory of Computing}{ }\else{Theory Comput.}\fi}%
\newcommand{\cjtcs }{\if\lName1\skp{ }{Chicago Journal of Theoretical Computer Science}{}\else{Chicago J. Theoret. Comput. Sci.}\fi}%
\newcommand{\mathprogram }{\if\lName1\skp{ }{Mathematical Programming}{}\else{Math. Program.}\fi}%
\newcommand{\mathcomput }{\if\lName1\skp{ }{Mathematics of Computation}{}\else{Math. Comput.}\fi}%
\newcommand{\jfourieranalappl }{\if\lName1\skp{ }{Journal of Fourier Analysis and Applications}{}\else{J. Fourier Anal. Appl.}\fi}%
\newcommand{\dcg }{\if\lName1\skp{ }{Discrete \& Computational Geometry}{}\else{Discrete Comput. Geom.}\fi}%
\newcommand{\randstructalg }{\if\lName1\skp{ }{Random Structures \& Algorithms}{}\else{Rand. Struct. Algorithms}\fi}%
\newcommand{\intjunconvent }{\if\lName1\skp{ }{International Journal of Unconventional Computing}{}\else{Int. J. Unconv. Comput.}\fi}%
\newcommand{\machlearnscitech }{\if\lName1\skp{ }{Machine Learning: Science and Technology}{}\else{Mach. Learn.: Sci. Technol.}\fi}%
\newcommand{\neuralprocesslett }{\if\lName1\skp{ }{Neural Processing Letters}{}\else{Neural Process. Lett.}\fi}%
\newcommand{\neuralcomput }{\if\lName1\skp{ }{Neural Computation}{}\else{Neural Comput.}\fi}%
\newcommand{\frontartifintell}{\if\lName1\skp{ }{Frontiers in Artificial Intelligence}{}\else{Front. Artif. Intell.}\fi}%
\newcommand{\jgloboptim}{\if\lName1\skp{ }{Journal of Global Optimization}{}\else{J. Glob. Optim.}\fi}%
\newcommand{\epjdatasci}{\if\lName1\skp{ }{EPJ Data Science}{}\else{EPJ Data Sci.}\fi}%
\newcommand{\epjquantumtechnol}{\if\lName1\skp{ }{EPJ Quantum Technology}{}\else{EPJ Quantum Technol.}\fi}%
\newcommand{\applsci }{\if\lName1\skp{ }{Applied Sciences}{ }\else{Appl. Sci.}\fi}%
\newcommand{\applphysrev }{\if\lName1\skp{ }{Applied Physics Reviews}{ }\else{Appl. Phys. Rev.}\fi}%
\newcommand{\advquantumtechnol }{\if\lName1\skp{ }{Advanced Quantum Technologies}{ }\else{Adv. Quantum Technol.}\fi}%
\newcommand{\annphys }{\if\lName1\skp{ }{Annals of Physics}{ }\else{Ann. Phys.}\fi}%
\newcommand{\annualrevCMP }{\if\lName1\skp{ }{Annual Review of Condensed Matter Physics}{ }\else{Annu. Rev. Condens. Matter Phys.}\fi}%
\newcommand{\annualrevNPS }{\if\lName1\skp{ }{Annual Review of Nuclear and Particle Science}{ }\else{Annu. Rev. Nucl. Part. Sci.}\fi}%
\newcommand{\quantum }{\if\lName1\skp{ }{Quantum}{ }\else{Quantum}\fi}%
\newcommand{\quantumscitechnol }{\if\lName1\skp{ }{Quantum Science and Technology}{ }\else{Quantum Sci. Technol.}\fi}%
\newcommand{\cmp }{\if\lName1\skp{ }{Communications in Mathematical Physics}{ }\else{Commun. Math. Phys.}\fi}%
\newcommand{\frontphys }{\if\lName1\skp{ }{Frontiers in Physics}{ }\else{Front. Phys.}\fi}%
\newcommand{\jmp }{\if\lName1\skp{ }{Journal of Mathematical Physics}{ }\else{J. Math. Phys.}\fi}%
\newcommand{\rspa }{\if\lName1\skp{ }{Proceedings of the Royal Society A}{ }\else{Proc. R. Soc. A}\fi}%
\newcommand{\philostransroyal}{\if\lName1\skp{ }{Philosophical Transactions of the Royal Society A}{ }\else{Philos. Trans. R. Soc. A}\fi}%
\newcommand{\qic }{\if\lName1\skp{ }{Quantum Information and Computation}{ }\else{Quantum Inf. Comput.}\fi}%
\newcommand{\qip }{\if\lName1\skp{ }{Quantum Information Processing}{ }\else{Quantum Inf. Process.}\fi}%
\newcommand{\physrev }{\if\lName1\skp{ }{Physical Review}{ }\else{Phys. Rev.}\fi}%
\newcommand{\pra }{\if\lName1\skp{ }{Physical Review A}{ }\else{Phys. Rev. A}\fi}%
\newcommand{\prb }{\if\lName1\skp{ }{Physical Review B}{ }\else{Phys. Rev. B}\fi}%
\newcommand{\prc }{\if\lName1\skp{ }{Physical Review C}{ }\else{Phys. Rev. C}\fi}%
\newcommand{\prd }{\if\lName1\skp{ }{Physical Review D}{ }\else{Phys. Rev. D}\fi}%
\newcommand{\pre }{\if\lName1\skp{ }{Physical Review E}{ }\else{Phys. Rev. E}\fi}%
\newcommand{\prr }{\if\lName1\skp{ }{Physical Review Research}{ }\else{Phys. Rev. Res.}\fi}%
\newcommand{\prx }{\if\lName1\skp{ }{Physical Review X}{ }\else{Phys. Rev. X}\fi}%
\newcommand{\prxq }{\if\lName1\skp{ }{PRX Quantum}{ }\else{PRX Quantum}\fi}%
\newcommand{\prl }{\if\lName1\skp{ }{Physical Review Letters}{ }\else{Phys. Rev. Lett.}\fi}%
\newcommand{\europhyslett }{\if\lName1\skp{ }{Europhysics Letters}{ }\else{Europhys. Lett.}\fi}%
\newcommand{\epja }{\if\lName1\skp{ }{The European Physical Journal A}{ }\else{Euro. Phys. J. A}\fi}%
\newcommand{\epjd }{\if\lName1\skp{ }{The European Physical Journal D}{ }\else{Euro. Phys. J. D}\fi}%
\newcommand{\njp }{\if\lName1\skp{ }{New Journal of Physics}{ }\else{New J. Phys.}\fi}%
\newcommand{\prapp }{\if\lName1\skp{ }{Physical Review Applied}{ }\else{Phys. Rev. Appl.}\fi}%
\newcommand{\physrep }{\if\lName1\skp{ }{Physics Reports}{ }\else{Phys. Rep.}\fi}%
\newcommand{\rmp }{\if\lName1\skp{ }{Reviews of Modern Physics}{ }\else{Rev. Mod. Phys.}\fi}%
\newcommand{\repprogphys }{\if\lName1\skp{ }{Reports on Progress in Physics}{ }\else{Rep. Prog. Phys.}\fi}%
\newcommand{\physplasmas }{\if\lName1\skp{ }{Physics of Plasmas}{ }\else{Phys. Plasmas}\fi}%
\newcommand{\phystoday }{\if\lName1\skp{ }{Physics Today}{ }\else{Phys. Today}\fi}%
\newcommand{\physics }{\if\lName1\skp{ }{Physics}{ }\else{Phys.}\fi}%
\newcommand{\nature }{\if\lName1\skp{ }{Nature}{ }\else{Nature}\fi}%
\newcommand{\natcomm }{\if\lName1\skp{ }{Nature Communications}{ }\else{Nat. Commun.}\fi}%
\newcommand{\natcomputsci }{\if\lName1\skp{ }{Nature Computational Science}{ }\else{Nat. Comput. Sci.}\fi}%
\newcommand{\natphys }{\if\lName1\skp{ }{Nature Physics}{ }\else{Nat. Phys.}\fi}%
\newcommand{\natphotonics }{\if\lName1\skp{ }{Nature Photonics}{ }\else{Nat. Photonics}\fi}%
\newcommand{\natrevphys }{\if\lName1\skp{ }{Nature Reviews Physics}{ }\else{Nat. Rev. Phys.}\fi}%
\newcommand{\natrevmater }{\if\lName1\skp{ }{Nature Reviews Materials}{ }\else{Nat. Rev. Mater.}\fi}%
\newcommand{\natrevmethodsprimers}{\if\lName1\skp{}{Nature Reviews Methods Primers}{ }\else{Nat. Rev. Methods Primers}\fi}%
\newcommand{\npjqi }{\if\lName1\skp{ }{npj Quantum Information}{ }\else{npj Quant. Inf.}\fi}%
\newcommand{\scirep }{\if\lName1\skp{ }{Scientific Reports}{ }\else{Sci. Rep.}\fi}%
\newcommand{\science }{\if\lName1\skp{ }{Science}{ }\else{Science}\fi}%
\newcommand{\sciadv }{\if\lName1\skp{ }{Science Advances}{ }\else{Sci. Adv.}\fi}%
\newcommand{\scibull }{\if\lName1\skp{ }{Science Bulletin}{ }\else{Sci. Bull.}\fi}%
\newcommand{\jchemphys }{\if\lName1\skp{ }{The Journal of Chemical Physics}{ }\else{J. Chem. Phys.}\fi}%
\newcommand{\jphyschemlett }{\if\lName1\skp{ }{The Journal of Physical Chemistry Letters}{ }\else{J. Phys. Chem. Lett.}\fi}%
\newcommand{\jpa }{\if\lName1\skp{ }{Journal of Physics A: Mathematical and Theoretical}{ }\else{J. Phys. A}\fi}%
\newcommand{\jpg }{\if\lName1\skp{ }{Journal of Physics G: Nuclear and Particle Physics}{ }\else{J. Phys. G}\fi}%
\newcommand{\ijtp }{\if\lName1\skp{ }{International Journal of Theoretical Physics}{ }\else{Int. J. Th. Phys.}\fi}%
\newcommand{\jmo }{\if\lName1\skp{ }{Journal of Modern Optics}{ }\else{J. Mod. Opt.}\fi}%
\newcommand{\jhep }{\if\lName1\skp{ }{Journal of High Energy Physics}{ }\else{J. High Energy Phys.}\fi}%
\newcommand{\jstatph }{\if\lName1\skp{ }{Journal of Statistical Physics}{ }\else{J. Stat. Phys.}\fi}%
\newcommand{\jcompphys }{\if\lName1\skp{ }{Journal of Computational Physics}{ }\else{J. Comput. Phys.}\fi}%
\newcommand{\computphyscommun}{\if\lName1\skp{ }{Computer Physics Communications}{ }\else{Comput. Phys. Commun.}\fi}%
\newcommand{\jstatmech }{\if\lName1\skp{ }{Journal of Statistical Mechanics: Theory and Experiment}{ }\else{J. Stat. Mech. Theory Exp.}\fi}%
\newcommand{\pnas }{\if\lName1\skp{ }{Proceedings of the National Academy of Sciences}{ }\else{Proc. Natl. Acad. Sci.}\fi}%
\newcommand{\avsquantsci }{\if\lName1\skp{ }{AVS Quantum Science}{ }\else{AVS Quantum Sci.}\fi}%
\newcommand{\quantummachintell }{\if\lName1\skp{ }{Quantum Machine Intelligence}{ }\else{Quantum Mach. Intell.}\fi}%
\newcommand{\natmachintell }{\if\lName1\skp{ }{Nature Machine Intelligence}{ }\else{Nat. Mach. Intell.}\fi}%
\newcommand{\scichinainfsci }{\if\lName1\skp{ }{ Science China Information Sciences}{ }\else{Sci. China Inf. Sci.}\fi}%
\newcommand{\jmagnreson }{\if\lName1\skp{ }{Journal of Magnetic Resonance}{ }\else{J. Magn. Reson.}\fi}%
\newcommand{\lncs }{\if\lName1\skp{ }{Lecture Notes in Computer Science}{ }\else{L. Notes Comp. Sci.}\fi}%
\newcommand{\lnai }{\if\lName1\skp{ }{Lecture Notes in Artificial Intelligence}{ }\else{L. Notes Art. Int.}\fi}%
\newcommand{\lnm }{\if\lName1\skp{ }{Lecture Notes in Mathematics}{ }\else{L. Notes Math.}\fi}%
\newcommand{\tams }{\if\lName1\skp{ }{Transactions of the American Mathematical Society}{ }\else{Trans. AMS}\fi}%
\newcommand{\ieeetit }{\if\lName1\skp{ }{{IEEE} Transactions on Information Theory}{ }\else{{IEEE} Trans. Inf. Theory}\fi}%
\newcommand{\ieeetnnls }{\if\lName1\skp{ }{{IEEE} Transactions on Neural Networks and Learning Systems}{ }\else{{IEEE} Trans. Neural Netw. Learn. Syst.}\fi}%
\newcommand{\ieeetcad }{\if\lName1\skp{ }{{IEEE} Transactions on Computer-Aided Design of Integrated Circuits and Systems}{ }\else{{IEEE} Trans. Comput.-Aided Des. Integr. Circuits Syst.}\fi}%
\newcommand{\ieeetqe }{\if\lName1\skp{ }{{IEEE} Transactions on Quantum Engineering}{ }\else{{IEEE} Trans. Quantum Eng.}\fi}%
\newcommand{\ieeejsac }{\if\lName1\skp{ }{{IEEE} Journal on Selected Areas in Communications}{ }\else{{IEEE} J. Sel. Areas Commun.}\fi}%
\newcommand{\ieeebits }{\if\lName1\skp{ }{{IEEE} {BITS} the Information Theory Magazine}{ }\else{{IEEE} {BITS} Inf. Theory Mag.}\fi}%
\newcommand{\quantumeng }{\if\lName1\skp{ }{Quantum Engineering}{ }\else{Quantum Eng.}\fi}%
\newcommand{\iscs }{\if\lName1\skp{ }{International Series in Computer Science}{ }\else{Int. Ser. Comp. Sci.}\fi}%
\newcommand{\tocl }{\if\lName1\skp{ }{Theory of Computing Library}{ }\else{Th. Comp. Lib.}\fi}%
\newcommand{\actanumer }{\if\lName1\skp{ }{Acta Numerica}{ }\else{Acta Numer.}\fi}%
\newcommand{\jderiv }{\if\lName1\skp{ }{The Journal of Derivatives}{ }\else{J. Deriv.}\fi}%
\newcommand{\chemrev }{\if\lName1\skp{ }{Chemical Reviews}{ }\else{Chem. Rev.}\fi}%
\newcommand{\WIREsCMS }{\if\lName1\skp{ }{WIREs Molecular Computational Science}{ }\else{WIREs Comput. Mol. Sci.}\fi}%
\newcommand{\accchemres }{\if\lName1\skp{ }{Accounts of Chemical Research}{ }\else{Acc. Chem. Res.}\fi}%
\newcommand{\chemphyslett }{\if\lName1\skp{ }{Chemical Physics Letters}{ }\else{Chem. Phys. Lett.}\fi}%
\newcommand{\molphys }{\if\lName1\skp{ }{Molecular Physics}{ }\else{Mol. Phys.}\fi}%
\newcommand{\commchem }{\if\lName1\skp{ }{Communications Chemistry}{ }\else{Commun. Chem.}\fi}%
\newcommand{\acscentsci }{\if\lName1\skp{ }{ACS Central Science}{ }\else{ACS Cent. Sci.}\fi}%
\newcommand{\jchemtheorycomput}{\if\lName1\skp{ }{Journal of Chemical Theory and Computation}{ }\else{J. Chem. Theory Comput.}\fi}%
\newcommand{\chemsci }{\if\lName1\skp{ }{Chemical Science}{ }\else{Chem. Sci.}\fi}%
\newcommand{\intjqchem }{\if\lName1\skp{ }{International journal of quantum chemistry}{ }\else{Int. J. Quantum Chem.}\fi}%
\newcommand{\jfqa }{\if\lName1\skp{ }{Journal of Financial and Quantitative Analysis}{ }\else{J. Financial Quant. Anal.}\fi}%

\refsection{0}
\datalist[entry]{none/global//global/global}
\entry{harrow2009QLinSysSolver}{article}{}
\name{author}{3}{}{%
given={Aram\bibnamedelima W.},
giveni={A\bibinitperiod\bibinitdelim W\bibinitperiod}}}%
\strng{namehash}{3b3176c8c71f2d0502e9279289094069}
\strng{fullhash}{3b3176c8c71f2d0502e9279289094069}
\strng{bibnamehash}{3b3176c8c71f2d0502e9279289094069}
\strng{authorbibnamehash}{3b3176c8c71f2d0502e9279289094069}
\strng{authornamehash}{3b3176c8c71f2d0502e9279289094069}
\strng{authorfullhash}{3b3176c8c71f2d0502e9279289094069}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\prl}
\field{note}{\arxiv{0811.3171}}
\field{number}{15}
\field{title}{Quantum algorithm for linear systems of equations}
\field{volume}{103}
\field{year}{2009}
\field{pages}{150502}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PhysRevLett.103.150502
\endverb
\endentry
\entry{babbush2021FocusBeyondQuadratic}{article}{}
\name{author}{6}{}{%
given={Jarrod\bibnamedelima R.},
giveni={J\bibinitperiod\bibinitdelim R\bibinitperiod}}}%
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{1bbad31b8888060615c18a9afec79cfc}
\strng{fullhash}{1bbad31b8888060615c18a9afec79cfc}
\strng{bibnamehash}{1bbad31b8888060615c18a9afec79cfc}
\strng{authorbibnamehash}{1bbad31b8888060615c18a9afec79cfc}
\strng{authornamehash}{1bbad31b8888060615c18a9afec79cfc}
\strng{authorfullhash}{1bbad31b8888060615c18a9afec79cfc}
\field{sortinit}{2}
\field{sortinithash}{8b555b3791beccb63322c22f3320aa9a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\prxq}
\field{month}{3}
\field{note}{\arxiv{2011.04149}}
\field{number}{1}
\field{title}{Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage}
\field{volume}{2}
\field{year}{2021}
\field{pages}{010103}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PRXQuantum.2.010103
\endverb
\endentry
\entry{ambainis2010VTAA}{inproceedings}{}
\name{author}{1}{}{%
\strng{namehash}{e31a92768d141b505fd318b971262b73}
\strng{fullhash}{e31a92768d141b505fd318b971262b73}
\strng{bibnamehash}{e31a92768d141b505fd318b971262b73}
\strng{authorbibnamehash}{e31a92768d141b505fd318b971262b73}
\strng{authornamehash}{e31a92768d141b505fd318b971262b73}
\strng{authorfullhash}{e31a92768d141b505fd318b971262b73}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\stacs{29th}}
\field{note}{\arxiv{1010.4458}}
\field{title}{Variable time amplitude amplification and quantum algorithms for linear algebra problems}
\field{year}{2012}
\field{pages}{636\bibrangedash 647}
\range{pages}{12}
\verb{doi}
\verb 10.4230/LIPIcs.STACS.2012.636
\endverb
\endentry
\entry{childs2015QLinSysExpPrec}{article}{}
\name{author}{3}{}{%
given={Andrew\bibnamedelima M.},
giveni={A\bibinitperiod\bibinitdelim M\bibinitperiod}}}%
given={Rolando\bibnamedelima D.},
giveni={R\bibinitperiod\bibinitdelim D\bibinitperiod}}}%
\strng{namehash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\strng{fullhash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\strng{bibnamehash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\strng{authorbibnamehash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\strng{authornamehash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\strng{authorfullhash}{af7dfeff67aab7c4b6720c6eb1d8c388}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\siamjc}
\field{note}{\arxiv{1511.02306}}
\field{number}{6}
\field{title}{Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision}
\field{volume}{46}
\field{year}{2017}
\field{pages}{1920\bibrangedash 1950}
\range{pages}{31}
\verb{doi}
\verb 10.1137/16M1087072
\endverb
\endentry
\entry{chakraborty2018BlockMatrixPowers}{inproceedings}{}
\name{author}{3}{}{%
\strng{namehash}{41661a872c226541281511b54adb96b6}
\strng{fullhash}{41661a872c226541281511b54adb96b6}
\strng{bibnamehash}{41661a872c226541281511b54adb96b6}
\strng{authorbibnamehash}{41661a872c226541281511b54adb96b6}
\strng{authornamehash}{41661a872c226541281511b54adb96b6}
\strng{authorfullhash}{41661a872c226541281511b54adb96b6}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\icalp{46th}}
\field{note}{\arxiv{1804.01973}}
\field{title}{The power of block-encoded matrix powers: {I}mproved regression techniques via faster {H}amiltonian simulation}
\field{year}{2019}
\field{pages}{33:1\bibrangedash 33:14}
\range{pages}{-1}
\verb{doi}
\verb 10.4230/LIPIcs.ICALP.2019.33
\endverb
\endentry
\entry{subasi2019QAlgSysLinEqsAdiabatic}{article}{}
\name{author}{3}{}{%
given={Rolando\bibnamedelima D.},
giveni={R\bibinitperiod\bibinitdelim D\bibinitperiod}}}%
\strng{namehash}{0ed1fa01c54d40385ab04fc09c49198a}
\strng{fullhash}{0ed1fa01c54d40385ab04fc09c49198a}
\strng{bibnamehash}{0ed1fa01c54d40385ab04fc09c49198a}
\strng{authorbibnamehash}{0ed1fa01c54d40385ab04fc09c49198a}
\strng{authornamehash}{0ed1fa01c54d40385ab04fc09c49198a}
\strng{authorfullhash}{0ed1fa01c54d40385ab04fc09c49198a}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\prl}
\field{note}{\arxiv{1805.10549}}
\field{number}{6}
\field{title}{Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing}
\field{volume}{122}
\field{year}{2019}
\field{pages}{060504}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PhysRevLett.122.060504
\endverb
\endentry
\entry{an2022QLSStimeDepAdiabatic}{article}{}
\name{author}{2}{}{%
\list{location}{1}{%
{New York, NY, USA}%
\list{publisher}{1}{%
{Association for Computing Machinery}%
\strng{namehash}{94db70e178472e1b7d71eb7f7aa06f8f}
\strng{fullhash}{94db70e178472e1b7d71eb7f7aa06f8f}
\strng{bibnamehash}{94db70e178472e1b7d71eb7f7aa06f8f}
\strng{authorbibnamehash}{94db70e178472e1b7d71eb7f7aa06f8f}
\strng{authornamehash}{94db70e178472e1b7d71eb7f7aa06f8f}
\strng{authorfullhash}{94db70e178472e1b7d71eb7f7aa06f8f}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\acmtqc}
\field{note}{\arxiv{1909.05500}}
\field{number}{2}
\field{title}{Quantum Linear System Solver Based on Time-Optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm}
\field{volume}{3}
\field{year}{2022}
\verb{doi}
\verb 10.1145/3498331
\endverb
\endentry
\entry{lin2019OptimalQEigenstateFiltering}{article}{}
\name{author}{2}{}{%
\strng{namehash}{5e5794cb74eaf39da901fb21df4e6847}
\strng{fullhash}{5e5794cb74eaf39da901fb21df4e6847}
\strng{bibnamehash}{5e5794cb74eaf39da901fb21df4e6847}
\strng{authorbibnamehash}{5e5794cb74eaf39da901fb21df4e6847}
\strng{authornamehash}{5e5794cb74eaf39da901fb21df4e6847}
\strng{authorfullhash}{5e5794cb74eaf39da901fb21df4e6847}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\quantum}
\field{note}{\arxiv{1910.14596}}
\field{title}{Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems}
\field{volume}{4}
\field{year}{2020}
\field{pages}{361}
\range{pages}{1}
\verb{doi}
\verb 10.22331/q-2020-11-11-361
\endverb
\endentry
\entry{costa2021OptimalLinearSystem}{article}{}
\name{author}{6}{}{%
given={Pedro\bibnamedelima C.S.},
giveni={P\bibinitperiod\bibinitdelim C\bibinitperiod}}}%
given={Yuval\bibnamedelima R.},
giveni={Y\bibinitperiod\bibinitdelim R\bibinitperiod}}}%
given={Dominic\bibnamedelima W.},
giveni={D\bibinitperiod\bibinitdelim W\bibinitperiod}}}%
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{bf391ba51042bc175000808f2d775f87}
\strng{fullhash}{bf391ba51042bc175000808f2d775f87}
\strng{bibnamehash}{bf391ba51042bc175000808f2d775f87}
\strng{authorbibnamehash}{bf391ba51042bc175000808f2d775f87}
\strng{authornamehash}{bf391ba51042bc175000808f2d775f87}
\strng{authorfullhash}{bf391ba51042bc175000808f2d775f87}
\field{sortinit}{4}
\field{sortinithash}{9381316451d1b9788675a07e972a12a7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issue}{4}
\field{journaltitle}{\prxq}
\field{month}{10}
\field{note}{\arXiv{2111.08152}}
\field{title}{Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem}
\field{volume}{3}
\field{year}{2022}
\field{pages}{040303}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PRXQuantum.3.040303
\endverb
\verb{urlraw}
\verb https://link.aps.org/doi/10.1103/PRXQuantum.3.040303
\endverb
\verb{url}
\verb https://link.aps.org/doi/10.1103/PRXQuantum.3.040303
\endverb
\endentry
\entry{Orsucci2021solvingclassesof}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
{Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften}%
\strng{namehash}{e468b16849a8c0a0ecc3c05078381e65}
\strng{fullhash}{e468b16849a8c0a0ecc3c05078381e65}
\strng{bibnamehash}{e468b16849a8c0a0ecc3c05078381e65}
\strng{authorbibnamehash}{e468b16849a8c0a0ecc3c05078381e65}
\strng{authornamehash}{e468b16849a8c0a0ecc3c05078381e65}
\strng{authorfullhash}{e468b16849a8c0a0ecc3c05078381e65}
\field{sortinit}{6}
\field{sortinithash}{b33bc299efb3c36abec520a4c896a66d}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issn}{2521-327X}
\field{journaltitle}{\quantum}
\field{month}{11}
\field{note}{\arxiv{2101.11868}}
\field{title}{On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number}
\field{volume}{5}
\field{year}{2021}
\field{pages}{573}
\range{pages}{1}
\verb{doi}
\verb 10.22331/q-2021-11-08-573
\endverb
\verb{urlraw}
\verb https://doi.org/10.22331/q-2021-11-08-573
\endverb
\verb{url}
\verb https://doi.org/10.22331/q-2021-11-08-573
\endverb
\endentry
\entry{albash2018AQCreview}{article}{}
\name{author}{2}{}{%
given={Daniel\bibnamedelima A.},
giveni={D\bibinitperiod\bibinitdelim A\bibinitperiod}}}%
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{eef612b545738e85d90651497a95b7cd}
\strng{fullhash}{eef612b545738e85d90651497a95b7cd}
\strng{bibnamehash}{eef612b545738e85d90651497a95b7cd}
\strng{authorbibnamehash}{eef612b545738e85d90651497a95b7cd}
\strng{authornamehash}{eef612b545738e85d90651497a95b7cd}
\strng{authorfullhash}{eef612b545738e85d90651497a95b7cd}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issue}{1}
\field{journaltitle}{\rmp}
\field{month}{1}
\field{note}{\arxiv{1611.04471}}
\field{title}{Adiabatic quantum computation}
\field{volume}{90}
\field{year}{2018}
\field{pages}{015002}
\range{pages}{1}
\verb{doi}
\verb 10.1103/RevModPhys.90.015002
\endverb
\endentry
\entry{jennings2023QLSS}{unpublished}{}
\name{author}{5}{}{%
given={Andrew\bibnamedelima T.},
giveni={A\bibinitperiod\bibinitdelim T\bibinitperiod}}}%
\strng{namehash}{976621e294a7318c322e5fcf7cc2a190}
\strng{fullhash}{976621e294a7318c322e5fcf7cc2a190}
\strng{bibnamehash}{976621e294a7318c322e5fcf7cc2a190}
\strng{authorbibnamehash}{976621e294a7318c322e5fcf7cc2a190}
\strng{authornamehash}{976621e294a7318c322e5fcf7cc2a190}
\strng{authorfullhash}{976621e294a7318c322e5fcf7cc2a190}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{\arxiv{2305.11352}}
\field{title}{Efficient quantum linear solver algorithm with detailed running costs}
\field{year}{2023}
\endentry
\entry{dalzell2022socp}{article}{}
\name{author}{11}{}{%
given={Alexander\bibnamedelima M.},
giveni={A\bibinitperiod\bibinitdelim M\bibinitperiod}}}%
given={B.\bibnamedelimi David},
giveni={B\bibinitperiod\bibinitdelim D\bibinitperiod}}}%
given={Cedric\bibnamedelima Yen-Yu},
giveni={C\bibinitperiod\bibinitdelim Y\bibinithyphendelim Y\bibinitperiod}}}%
given={David\bibnamedelima A.},
giveni={D\bibinitperiod\bibinitdelim A\bibinitperiod}}}%
given={Martin\bibnamedelimb J.\bibnamedelimi A.},
giveni={M\bibinitperiod\bibinitdelim J\bibinitperiod\bibinitdelim A\bibinitperiod}}}%
given={Fernando\bibnamedelimb G.\bibnamedelimi S.\bibnamedelimi L.},
giveni={F\bibinitperiod\bibinitdelim G\bibinitperiod\bibinitdelim S\bibinitperiod\bibinitdelim L\bibinitperiod}}}%
given={Helmut\bibnamedelima G.},
giveni={H\bibinitperiod\bibinitdelim G\bibinitperiod}}}%
given={William\bibnamedelima J.},
giveni={W\bibinitperiod\bibinitdelim J\bibinitperiod}}}%
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\strng{fullhash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\strng{bibnamehash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\strng{authorbibnamehash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\strng{authornamehash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\strng{authorfullhash}{c4fcf8b7fd3701a9c44c01760983a3d4}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issue}{4}
\field{journaltitle}{\prxq}
\field{month}{11}
\field{note}{\arXiv{2211.12489}}
\field{title}{End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization}
\field{volume}{4}
\field{year}{2023}
\field{pages}{040325}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PRXQuantum.4.040325
\endverb
\verb{urlraw}
\verb https://link.aps.org/doi/10.1103/PRXQuantum.4.040325
\endverb
\verb{url}
\verb https://link.aps.org/doi/10.1103/PRXQuantum.4.040325
\endverb
\endentry
\entry{jennings2023costDiffEQ}{unpublished}{}
\name{author}{5}{}{%
given={Robert\bibnamedelima B.},
giveni={R\bibinitperiod\bibinitdelim B\bibinitperiod}}}%
given={Andrew\bibnamedelima T.},
giveni={A\bibinitperiod\bibinitdelim T\bibinitperiod}}}%
\strng{namehash}{a56a8df1fabc236cf16df39d0b32135b}
\strng{fullhash}{a56a8df1fabc236cf16df39d0b32135b}
\strng{bibnamehash}{a56a8df1fabc236cf16df39d0b32135b}
\strng{authorbibnamehash}{a56a8df1fabc236cf16df39d0b32135b}
\strng{authornamehash}{a56a8df1fabc236cf16df39d0b32135b}
\strng{authorfullhash}{a56a8df1fabc236cf16df39d0b32135b}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{\arxiv{2309.07881}}
\field{title}{The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts}
\field{year}{2023}
\endentry
\entry{costa2023discreteConstantFactors}{unpublished}{}
\name{author}{4}{}{%
given={Pedro\bibnamedelimb C.\bibnamedelimi S.},
giveni={P\bibinitperiod\bibinitdelim C\bibinitperiod\bibinitdelim S\bibinitperiod}}}%
\strng{namehash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\strng{fullhash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\strng{bibnamehash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\strng{authorbibnamehash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\strng{authornamehash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\strng{authorfullhash}{b1e04a9ad54e0709bd49b454fa7e5dd0}
\field{sortinit}{1}
\field{sortinithash}{4f6aaa89bab872aa0999fec09ff8e98a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{\arxiv{2312.07690}}
\field{title}{The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver}
\field{year}{2023}
\endentry
\entry{gilyen2018QSingValTransf}{inproceedings}{}
\name{author}{4}{}{%
given={Guang\bibnamedelima Hao},
giveni={G\bibinitperiod\bibinitdelim H\bibinitperiod}}}%
\strng{namehash}{2318e6c69d33e8d0424ac51d525f90a5}
\strng{fullhash}{2318e6c69d33e8d0424ac51d525f90a5}
\strng{bibnamehash}{2318e6c69d33e8d0424ac51d525f90a5}
\strng{authorbibnamehash}{2318e6c69d33e8d0424ac51d525f90a5}
\strng{authornamehash}{2318e6c69d33e8d0424ac51d525f90a5}
\strng{authorfullhash}{2318e6c69d33e8d0424ac51d525f90a5}
\field{sortinit}{2}
\field{sortinithash}{8b555b3791beccb63322c22f3320aa9a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\stoc{51st}}
\field{note}{\arxiv{1806.01838}}
\field{title}{Quantum singular value transformation and beyond: {E}xponential improvements for quantum matrix arithmetics}
\field{year}{2019}
\field{pages}{193\bibrangedash 204}
\range{pages}{12}
\verb{doi}
\verb 10.1145/3313276.3316366
\endverb
\endentry
\entry{martyn2021GrandUnificationQAlgs}{article}{}
\name{author}{4}{}{%
given={John\bibnamedelima M.},
giveni={J\bibinitperiod\bibinitdelim M\bibinitperiod}}}%
given={Zane\bibnamedelima M.},
giveni={Z\bibinitperiod\bibinitdelim M\bibinitperiod}}}%
given={Andrew\bibnamedelima K.},
giveni={A\bibinitperiod\bibinitdelim K\bibinitperiod}}}%
given={Isaac\bibnamedelima L.},
giveni={I\bibinitperiod\bibinitdelim L\bibinitperiod}}}%
\strng{namehash}{18e5ccc3bf875ba8213f535a004dc611}
\strng{fullhash}{18e5ccc3bf875ba8213f535a004dc611}
\strng{bibnamehash}{18e5ccc3bf875ba8213f535a004dc611}
\strng{authorbibnamehash}{18e5ccc3bf875ba8213f535a004dc611}
\strng{authornamehash}{18e5ccc3bf875ba8213f535a004dc611}
\strng{authorfullhash}{18e5ccc3bf875ba8213f535a004dc611}
\field{sortinit}{2}
\field{sortinithash}{8b555b3791beccb63322c22f3320aa9a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\prx}
\field{note}{\arXiv{2105.02859}}
\field{number}{4}
\field{title}{Grand Unification of Quantum Algorithms}
\field{volume}{2}
\field{year}{2021}
\field{pages}{040203}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PRXQuantum.2.040203
\endverb
\endentry
\entry{knill2007ObservableMeasurement}{article}{}
\name{author}{3}{}{%
given={Rolando\bibnamedelima D.},
giveni={R\bibinitperiod\bibinitdelim D\bibinitperiod}}}%
\list{publisher}{1}{%
{American Physical Society}%
\strng{namehash}{8d4780cb931e6f489db6b4e030b58a44}
\strng{fullhash}{8d4780cb931e6f489db6b4e030b58a44}
\strng{bibnamehash}{8d4780cb931e6f489db6b4e030b58a44}
\strng{authorbibnamehash}{8d4780cb931e6f489db6b4e030b58a44}
\strng{authornamehash}{8d4780cb931e6f489db6b4e030b58a44}
\strng{authorfullhash}{8d4780cb931e6f489db6b4e030b58a44}
\field{sortinit}{2}
\field{sortinithash}{8b555b3791beccb63322c22f3320aa9a}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{issue}{1}
\field{journaltitle}{\pra}
\field{month}{1}
\field{note}{\arxiv{quant-ph/0607019}}
\field{title}{Optimal quantum measurements of expectation values of observables}
\field{volume}{75}
\field{year}{2007}
\field{pages}{012328}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PhysRevA.75.012328
\endverb
\verb{urlraw}
\verb https://link.aps.org/doi/10.1103/PhysRevA.75.012328
\endverb
\verb{url}
\verb https://link.aps.org/doi/10.1103/PhysRevA.75.012328
\endverb
\endentry
\entry{grover1996QSearch}{inproceedings}{}
\name{author}{1}{}{%
given={Lov\bibnamedelima K.},
giveni={L\bibinitperiod\bibinitdelim K\bibinitperiod}}}%
\strng{namehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{fullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{bibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorbibnamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authornamehash}{619ef89ee12058aba6b0df9b17b11ca3}
\strng{authorfullhash}{619ef89ee12058aba6b0df9b17b11ca3}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\stoc{28th}}
\field{note}{\arxiv{quant-ph/9605043}}
\field{title}{A Fast Quantum Mechanical Algorithm for Database Search}
\field{year}{1996}
\field{pages}{212\bibrangedash 219}
\range{pages}{8}
\verb{doi}
\verb 10.1145/237814.237866
\endverb
\endentry
\entry{yoder2014FixedPointSearch}{article}{}
\name{author}{3}{}{%
given={Theodore\bibnamedelima J.},
giveni={T\bibinitperiod\bibinitdelim J\bibinitperiod}}}%
given={Guang\bibnamedelima Hao},
giveni={G\bibinitperiod\bibinitdelim H\bibinitperiod}}}%
given={Isaac\bibnamedelima L.},
giveni={I\bibinitperiod\bibinitdelim L\bibinitperiod}}}%
\strng{namehash}{432bb8370459544051ce47e5e92995d4}
\strng{fullhash}{432bb8370459544051ce47e5e92995d4}
\strng{bibnamehash}{432bb8370459544051ce47e5e92995d4}
\strng{authorbibnamehash}{432bb8370459544051ce47e5e92995d4}
\strng{authornamehash}{432bb8370459544051ce47e5e92995d4}
\strng{authorfullhash}{432bb8370459544051ce47e5e92995d4}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\prl}
\field{note}{\arxiv{1409.3305}}
\field{number}{21}
\field{title}{Fixed-Point Quantum Search with an Optimal Number of Queries}
\field{volume}{113}
\field{year}{2014}
\field{pages}{210501}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PhysRevLett.113.210501
\endverb
\endentry
\entry{burnashev1974interval}{article}{}
\name{author}{2}{}{%
given={Marat\bibnamedelima Valievich},
giveni={M\bibinitperiod\bibinitdelim V\bibinitperiod}}}%
\list{publisher}{1}{%
{Russian Academy of Sciences, Branch of Informatics, Computer Equipment and~…}%
\strng{namehash}{09a79a873990bf32dd86197a29758607}
\strng{fullhash}{09a79a873990bf32dd86197a29758607}
\strng{bibnamehash}{09a79a873990bf32dd86197a29758607}
\strng{authorbibnamehash}{09a79a873990bf32dd86197a29758607}
\strng{authornamehash}{09a79a873990bf32dd86197a29758607}
\strng{authorfullhash}{09a79a873990bf32dd86197a29758607}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{Problemy Peredachi Informatsii}
\field{note}{In Russian, see \cite{wang2022noisySortingcapacity} for key proof in English}
\field{number}{3}
\field{title}{An interval estimation problem for controlled observations}
\field{volume}{10}
\field{year}{1974}
\field{pages}{51\bibrangedash 61}
\range{pages}{11}
\endentry
\entry{ben-or2008BayesianLearner}{inproceedings}{}
\name{author}{2}{}{%
familyi={B\bibinithyphendelim O\bibinitperiod},
\strng{namehash}{2d93d183f20833bea33a80543085ddbc}
\strng{fullhash}{2d93d183f20833bea33a80543085ddbc}
\strng{bibnamehash}{2d93d183f20833bea33a80543085ddbc}
\strng{authorbibnamehash}{2d93d183f20833bea33a80543085ddbc}
\strng{authornamehash}{2d93d183f20833bea33a80543085ddbc}
\strng{authorfullhash}{2d93d183f20833bea33a80543085ddbc}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{2008 49th Annual IEEE Symposium on Foundations of Computer Science}
\field{note}{\arxiv{quant-ph/0703231}}
\field{title}{The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well)}
\field{year}{2008}
\field{pages}{221\bibrangedash 230}
\range{pages}{10}
\verb{doi}
\verb 10.1109/FOCS.2008.58
\endverb
\keyw{Bayesian methods;Computer science;Quantum computing;Information theory;Error correction;Entropy;Error probability;search;noise;binary search;quantum search;algorithms}
\endentry
\entry{wang2022noisySortingcapacity}{inproceedings}{}
\name{author}{3}{}{%
\strng{namehash}{29070c7077e329db6499dc2e89fcacb3}
\strng{fullhash}{29070c7077e329db6499dc2e89fcacb3}
\strng{bibnamehash}{29070c7077e329db6499dc2e89fcacb3}
\strng{authorbibnamehash}{29070c7077e329db6499dc2e89fcacb3}
\strng{authornamehash}{29070c7077e329db6499dc2e89fcacb3}
\strng{authorfullhash}{29070c7077e329db6499dc2e89fcacb3}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\isit{2022}}
\field{note}{\arxiv{2202.01446}}
\field{title}{Noisy Sorting Capacity}
\field{year}{2022}
\field{pages}{2541\bibrangedash 2546}
\range{pages}{6}
\verb{doi}
\verb 10.1109/ISIT50566.2022.9834370
\endverb
\keyw{Error probability;Encoding;Noise measurement;Task analysis;Sorting}
\endentry
\entry{gretta2023sharpNoisyBinarySearch}{unpublished}{}
\name{author}{2}{}{%
\strng{namehash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\strng{fullhash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\strng{bibnamehash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\strng{authorbibnamehash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\strng{authornamehash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\strng{authorfullhash}{dced38bc3b546b2dbb7a5b3a444ab72f}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{\arxiv{2311.00840}}
\field{title}{Sharp Noisy Binary Search with Monotonic Probabilities}
\field{year}{2023}
\endentry
\entry{nagaj2009FastAmpQMA}{article}{}
\name{author}{3}{}{%
\strng{namehash}{742a4a1a17f15027414ea93f6d5f7068}
\strng{fullhash}{742a4a1a17f15027414ea93f6d5f7068}
\strng{bibnamehash}{742a4a1a17f15027414ea93f6d5f7068}
\strng{authorbibnamehash}{742a4a1a17f15027414ea93f6d5f7068}
\strng{authornamehash}{742a4a1a17f15027414ea93f6d5f7068}
\strng{authorfullhash}{742a4a1a17f15027414ea93f6d5f7068}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\qic}
\field{note}{\arxiv{0904.1549}}
\field{number}{11\&12}
\field{title}{Fast Amplification of {QMA}}
\field{volume}{9}
\field{year}{2009}
\field{pages}{1053\bibrangedash 1068}
\range{pages}{16}
\verb{doi}
\verb 10.26421/QIC9.11-12
\endverb
\endentry
\entry{kothari2023meanEstimationSourceCode}{inbook}{}
\name{author}{2}{}{%
\strng{namehash}{c3c304d6826910951397a3b15138067a}
\strng{fullhash}{c3c304d6826910951397a3b15138067a}
\strng{bibnamehash}{c3c304d6826910951397a3b15138067a}
\strng{authorbibnamehash}{c3c304d6826910951397a3b15138067a}
\strng{authornamehash}{c3c304d6826910951397a3b15138067a}
\strng{authorfullhash}{c3c304d6826910951397a3b15138067a}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{\soda{2023}}
\field{note}{\arxiv{2208.07544}}
\field{title}{Mean estimation when you have the source code; or, quantum Monte Carlo methods}
\field{year}{2023}
\field{pages}{1186\bibrangedash 1215}
\range{pages}{30}
\verb{doi}
\verb 10.1137/1.9781611977554.ch44
\endverb
\verb{eprint}
\verb https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch44
\endverb
\verb{urlraw}
\verb https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch44
\endverb
\verb{url}
\verb https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch44
\endverb
\endentry
\entry{brassard2002AmpAndEst}{incollection}{}
\name{author}{4}{}{%
\list{publisher}{1}{%
\strng{namehash}{260a71d5255a0117d78d042829019aa3}
\strng{fullhash}{260a71d5255a0117d78d042829019aa3}
\strng{bibnamehash}{260a71d5255a0117d78d042829019aa3}
\strng{authorbibnamehash}{260a71d5255a0117d78d042829019aa3}
\strng{authornamehash}{260a71d5255a0117d78d042829019aa3}
\strng{authorfullhash}{260a71d5255a0117d78d042829019aa3}
\field{sortinit}{3}
\field{sortinithash}{ad6fe7482ffbd7b9f99c9e8b5dccd3d7}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{booktitle}{Quantum Computation and Quantum Information: A Millennium Volume}
\field{note}{\arxiv{quant-ph/0005055}}
\field{series}{Contemporary Mathematics Series}
\field{title}{Quantum Amplitude Amplification and Estimation}
\field{volume}{305}
\field{year}{2002}
\field{pages}{53\bibrangedash 74}
\range{pages}{22}
\verb{doi}
\verb 10.1090/conm/305/05215
\endverb
\endentry
\entry{dalzell2023quantumAlgorithmsSurvey}{unpublished}{}
\name{author}{13}{}{%
given={Alexander\bibnamedelima M.},
giveni={A\bibinitperiod\bibinitdelim M\bibinitperiod}}}%
giveni={C\bibinithyphendelim F\bibinitperiod}}}%
given={Connor\bibnamedelima T.},
giveni={C\bibinitperiod\bibinitdelim T\bibinitperiod}}}%
given={Michael\bibnamedelima J.},
giveni={M\bibinitperiod\bibinitdelim J\bibinitperiod}}}%
given={Emil\bibnamedelima T.},
giveni={E\bibinitperiod\bibinitdelim T\bibinitperiod}}}%
given={Fernando\bibnamedelimb G.\bibnamedelimi S.\bibnamedelimi L.},
giveni={F\bibinitperiod\bibinitdelim G\bibinitperiod\bibinitdelim S\bibinitperiod\bibinitdelim L\bibinitperiod}}}%
\strng{namehash}{2e9e3ec89e7f54d4afad9d0664479c51}
\strng{fullhash}{75e47e2fe3020125b8700c6a5c91df94}
\strng{bibnamehash}{2e9e3ec89e7f54d4afad9d0664479c51}
\strng{authorbibnamehash}{2e9e3ec89e7f54d4afad9d0664479c51}
\strng{authornamehash}{2e9e3ec89e7f54d4afad9d0664479c51}
\strng{authorfullhash}{75e47e2fe3020125b8700c6a5c91df94}
\field{sortinit}{5}
\field{sortinithash}{20e9b4b0b173788c5dace24730f47d8c}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{note}{\arxiv{2310.03011}}
\field{title}{Quantum algorithms: A survey of applications and end-to-end complexities}
\field{year}{2023}
\endentry
\entry{berry2014highOrderQuantumAlgorithmDiffEQ}{article}{}
\name{author}{1}{}{%
given={Dominic\bibnamedelima W},
giveni={D\bibinitperiod\bibinitdelim W\bibinitperiod}}}%
\list{publisher}{1}{%
{IOP Publishing}%
\strng{namehash}{e0053050bdc2ad78d707462c41ad32d3}
\strng{fullhash}{e0053050bdc2ad78d707462c41ad32d3}
\strng{bibnamehash}{e0053050bdc2ad78d707462c41ad32d3}
\strng{authorbibnamehash}{e0053050bdc2ad78d707462c41ad32d3}
\strng{authornamehash}{e0053050bdc2ad78d707462c41ad32d3}
\strng{authorfullhash}{e0053050bdc2ad78d707462c41ad32d3}
\field{sortinit}{5}
\field{sortinithash}{20e9b4b0b173788c5dace24730f47d8c}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\jpa}
\field{month}{2}
\field{note}{\arxiv{1010.2745}}
\field{number}{10}
\field{title}{High-order quantum algorithm for solving linear differential equations}
\field{volume}{47}
\field{year}{2014}
\field{pages}{105301}
\range{pages}{1}
\verb{doi}
\verb 10.1088/1751-8113/47/10/105301
\endverb
\verb{urlraw}
\verb https://dx.doi.org/10.1088/1751-8113/47/10/105301
\endverb
\verb{url}
\verb https://dx.doi.org/10.1088/1751-8113/47/10/105301
\endverb
\endentry
\entry{montanaro2016quantum}{article}{}
\name{author}{2}{}{%
\list{publisher}{1}{%
\strng{namehash}{e20b2b4efb10ba186c1fb561e930371b}
\strng{fullhash}{e20b2b4efb10ba186c1fb561e930371b}
\strng{bibnamehash}{e20b2b4efb10ba186c1fb561e930371b}
\strng{authorbibnamehash}{e20b2b4efb10ba186c1fb561e930371b}
\strng{authornamehash}{e20b2b4efb10ba186c1fb561e930371b}
\strng{authorfullhash}{e20b2b4efb10ba186c1fb561e930371b}
\field{sortinit}{5}
\field{sortinithash}{20e9b4b0b173788c5dace24730f47d8c}
\field{labelnamesource}{author}
\field{labeltitlesource}{title}
\field{journaltitle}{\pra}
\field{note}{\arXiv{1512.05903}}
\field{number}{3}
\field{title}{Quantum algorithms and the finite element method}
\field{volume}{93}
\field{year}{2016}
\field{pages}{032324}
\range{pages}{1}
\verb{doi}
\verb 10.1103/PhysRevA.93.032324
\endverb
\endentry
\entry{clader2013preconditioned}{article}{}