An Optimal Quantum Linear Systems Algorithm

1 Introduction

• The QLSP asks for an approximate state proportional to x=A^-1b, given access to a sparse matrix and preparation of b's state.Source: §1 · p. 1
• The paper gives an improved block encoding for sparse matrices, with normalization and operator-norm error specified by its parameters.Source: §1 · p. 2
• The Hermitian-dilation approach resolves Berry and Childs's open question with an optimal O(√N) query bound for constant-error unitary implementation.Source: §1 · p. 2
• The QLSP has query complexity Θ(κ√d log(1/ϵ)), with matching upper and lower bounds.Source: §1.1 · p. 3

1.1 Overview of proof techniques

• The upper-bound construction splits a matrix-product equation using an intermediate vector, forms an enlarged system, and block encodes it with O(1) oracle queries.The enlarged system contains the original solution among its variables; the method loads individual matrix entries rather than whole rows.Source: §1.1 · p. 3
• The lower-bound proof combines parity over Θ(κ log(1/ϵ)) independent search instances of size Θ(d), yielding an Ω(κ√d log(1/ϵ)) bound.The quantum XOR lemma preserves hardness despite the small advantage available when reading the answer from the history state.Source: §1.1 · p. 3

Concurrent Work

• In concurrent work, Patel [Pat26] also obtains the Ω(κ√d log(1/ϵ)) lower bound in the sparse-matrix access model.Source: Concurrent Work · p. 4

2.1 The standard sparse-matrix oracle to block-encoding reduction

• The standard sparse-matrix construction gives an exact block encoding of A/d and uses O(κd log(1/ϵ)) sparse-matrix oracle queries; an O(1)-query block encoding of A/d would exactly provide the desired improvement.Source: §2.1 · p. 6
• Directly preparing F|i⟩ could reveal the unknown position of a near-unit row entry, requiring Ω(d) queries and losing the desired complexity improvement.The construction instead assigns separate variables to the listed equation-variable pairs and lets the linear-system solver perform the sum.Source: §2.1 · p. 6, §2.2 · p. 6

2.2 A larger linear system

• The larger system replaces each original variable with d listed copies, encoding the product as two equations while preserving the desired solution direction.The first equations impose z=Tu and the second impose F†z=b.Source: §2.2 · pp. 6–7
• The matrix L is invertible with condition number O(κ), but its F† block prevents direct block encoding with the desired oracle cost.The section modifies L to avoid implementing F† directly while preserving the inverse bound and solution.Source: §2.2 · p. 7

2.3 Block encoding the larger linear system

• An exact block encoding of M with normalization factor 1 uses O(1) sparse-matrix oracle queries, and ∥M∥≤1.The maps are implemented coherently using location and value queries, without directly implementing F.Source: §2.3 · p. 9
• The bottom component of the normalized solution to the enlarged system remains proportional to A^-1b, while only the top component changes from Tu to QTu.The bottom component can be recovered by measurement; the analysis bounds ∥QT∥ to ensure constant-probability recovery.Source: §2.3 · p. 9, §2.4 · p. 9

3 Matching lower bound for the QLSP

• The lower bound matches the query complexity of the quantum algorithm, establishing a matching bound for the QLSP.Theorem 10 states that any quantum algorithm solving the QLSP must make the lower-bound number of queries.Source: §3 · p. 10

3.1 Circuit histories as linear systems

• The clock applies the circuit, idles while its output is stored, and then uncomputes, forming a cyclic history-state construction.The clock unitary advances one step at a time and is unitary under the cyclic convention.Source: §3.1 · pp. 10–11
• The inverse of a simple linear operator built from the clock unitary prepares a geometrically weighted history state whose useful interval is the idle period.The construction embeds the circuit into a linear system with the input state as its right-hand side.Source: §3.1 · pp. 10–11
• Conditioned on a middle-interval clock outcome, the data register is exactly the circuit output state.The clock states at distinct times are orthogonal, and the idle interval is where the data register holds the output.Source: §3.1 · p. 12

3.2 Warm-up lower bounds

• The warm-ups identify sparse unstructured search as the source of a √d lower-bound factor, and clock-history decay as the source of κ log(1/ϵ).The two warm-ups explain the factors in the final construction but are not separate theorems needed for its proof.Source: §3.2 · p. 12

3.2.1 Sparsity from unstructured search

• Embedding a one-gate circuit for hidden-shift search into a QLSP instance yields an Ω(√d) sparsity lower bound, up to an additive shift in d.The location oracle reveals no information about the hidden shift; the value oracle carries the input dependence.Source: §3.2.1 · p. 12

3.2.2 Condition number and precision from parity

• A parity circuit of length T gives the κ log(1/ϵ) dependence because its useful clock signal remains larger than the allowed trace-distance error.Parity requires Ω(T) queries for any success probability strictly above one half.Source: §3.2.2 · p. 13

3.2.3 Toward the joint lower bound

• The joint construction uses search to obtain Boolean bits and takes their parity, choosing the parity length so the clock signal exceeds the allowed error.Because the useful-clock probability decays exponentially in R/κ, the quantum XOR lemma handles the small advantage over random guessing.Source: §3.2.3 · p. 13

• The standard quantum lower bound for unstructured search supplies the hardness underlying the Boolean construction.Source: §3.3 · p. 14
• FR,D applies the left-right decision LRD to each of R blocks, each containing exactly one marked position.LRD returns 0 for a mark in the left half and 1 for a mark in the right half; FR,D uses the resulting bits.Source: §3.3 · p. 14
• The Lee–Roland quantum XOR lemma yields a small-advantage lower bound for FR,D for every fixed 0 < c < 1/2.The proof applies the lemma to LRD and uses Eq. (65).Source: §3.3 · p. 14

• For each block yi, the unique marked position defines a cyclic shift that can be simulated using one query to yi.Source: §3.4 · p. 14
• The data register consists of an address register and an answer qubit, and the construction also uses a fixed unitary B.Source: §3.4 · pp. 14–15
• The circuit Cy has length 3R and computes FR,D exactly on the initial zeroed address and answer registers.Processing all R blocks leaves the answer qubit holding the XOR of their left-right bits.Source: §3.4 · p. 15

• The reduction embeds the exact circuit for FR,D into a matrix instance using the circuit-to-matrix construction.The construction uses an input state with clock, address, and answer registers.Source: §3.5 · p. 15
• A solver’s successful output is measured on a middle clock interval, where the answer qubit yields FR,D(y); outside that interval, the procedure returns a random bit.The success probability is related to the probability of the middle clock event, and replacing the exact state by the solver’s output changes measurement success by at most the stated trace distance.Source: §3.5 · p. 16
• The construction extends to a Hermitian QLSP instance by Hermitian dilation without altering the relevant solution state.Source: §3.5 · p. 17
• Combining Theorems 4 and 10 gives the optimal query complexity and proves the paper’s main result.Source: §3.5 · p. 17

• The reduction that produces A−1|b⟩ also yields a constant-error block encoding of a Hermitian sparse matrix.Source: §4 · p. 17
• An inverse of a well-conditioned Hermitian sparse matrix can be block encoded with O(√s log(1/η)) oracle queries when its norm is at most 1 and its inverse norm is bounded by κ = O(1).The factor √s in the inverse block cancels the sparsity dependence of the inversion normalization.Source: §4 · p. 17
• The sparse-matrix block encoding uses a larger well-conditioned system whose inverse contains the target matrix as a block.The construction introduces variables enforcing v=b and u−Hv=0, then selects the appropriate block and adjusts the normalization.Source: §4 · p. 18
• An (O(1), η) block encoding of a Hermitian d-sparse matrix H with norm at most 1 uses O(√d log(1/η)) sparse-matrix oracle queries.Source: §4 · p. 18
• The paper resolves Berry and Childs’ open problem on implementing a unitary from entry-oracle access with bounded error.The stated construction uses a Hermitian dilation and an encoded block derived from it.Source: §4 · p. 18