Toward speedup without quantum coherent access

1. Problem Statement

The paper addresses critical bottlenecks hindering the practical application of quantum algorithms, specifically focusing on input assumptions and complexity scaling:

• The QRAM Bottleneck: Most prominent quantum algorithms (e.g., HHL for linear systems, LMR for PCA) rely on the assumption that classical data can be loaded into a quantum state via Quantum Random Access Memory (QRAM) in $O(\log N)$ time. Large-scale, fault-tolerant QRAM is currently hardware-prohibitive and unproven.
• Dequantization: Recent results by Ewin Tang have shown that many quantum algorithms (like PCA) offer no advantage over classical algorithms if the classical algorithm is allowed similar query access (specifically $l_2$-norm sampling).
• Sparsity and Error Scaling: Existing quantum algorithms for dense matrices or data fitting often exhibit poor scaling with respect to sparsity ($s$) and error tolerance ($\epsilon$). For instance, previous data fitting algorithms scale polynomially with $s$ and have high dependence on $1/\epsilon$.
• Output Utility: Many quantum algorithms output quantum states, making the extraction of useful classical information (via tomography) costly, often negating the speedup.

Goal: The author proposes a framework that achieves exponential speedups for various problems without requiring QRAM or coherent quantum access to the input data, relying instead on classical pre-processing of known matrix/vector entries.

2. Methodology

The core of the proposed methodology is a hybrid classical-quantum approach centered on Block-Encoding and State Preparation.

A. Classical Pre-processing & Block-Encoding

Instead of assuming an oracle provides quantum access to data, the algorithm assumes the classical entries of the matrix $A$ (or vector) are known.

1. State Preparation: A classical procedure preprocesses the entries of $A$ to construct a quantum circuit that prepares a specific state $|A\rangle = \frac{1}{\|A\|_F} \sum A_{ji} |j\rangle|i\rangle$.
2. Block-Encoding Construction: Using state preparation protocols (e.g., [ZLY22]) and Quantum Singular Value Transformation (QSVT) tools, the authors construct a unitary $U$ that block-encodes the matrix $A$.
   • $U = \begin{pmatrix} A & \cdot \\ \cdot & \cdot \end{pmatrix}$.
   • Crucially, the complexity of constructing this block-encoding depends on the structure of the matrix (e.g., sparsity, tensor product structure) and the Frobenius norm $\|A\|_F$, but not on the dimension $N$ in a way that requires QRAM.
   • The classical preprocessing cost is a one-time overhead (logarithmic or constant time depending on structure) and does not scale with the number of algorithm runs.

B. Algorithmic Framework

Once the block-encoding of the matrix is established, the authors leverage standard QSVT techniques to perform operations:

• Polynomial Transformation: Transforming $A$ to $P(A)$ (e.g., $A^{-1}$, $e^{-iHt}$).
• Power Method & Gradient Descent: Used for finding eigenvalues/eigenvectors (PCA).
• Imaginary Time Evolution: Used for ground state preparation.
• Linear Solving: Inverting matrices to solve $Ax=b$.

3. Key Contributions and Results

The paper presents six main results, demonstrating exponential or super-polynomial improvements over existing methods in specific regimes:

1. Efficient State Preparation for Structured States

• Contribution: Identifies a new class of states $|\Phi\rangle = \sum \alpha_i |\psi_{i1}\rangle \otimes \dots \otimes |\psi_{ik}\rangle$ where entries are classically known.
• Result: These states can be prepared with logarithmic circuit depth and $O(\log s)$ ancilla qubits (where $s$ is sparsity), significantly reducing resource requirements compared to general state preparation which often requires ancilla proportional to the number of non-zero entries.

2. Quantum Principal Component Analysis (QPCA)

• Method: Combines the block-encoding of the covariance matrix with the Quantum Power Method.
• Complexity: $O(\log(mn) \cdot \text{polylog}(1/\epsilon))$.
• Improvement: Achieves exponential speedup in the inverse error tolerance ($1/\epsilon$) and the number of samples ($m$) compared to [LMR14] and [Ngh25a]. It avoids the linear scaling in $m$ found in previous power-method-based approaches.

3. Quantum Linear System Algorithm (QLSA)

• Method: Block-encodes $A$ and uses QSVT to invert it.
• Complexity: $O(\|A\|_F \kappa^2 \log(sn) \text{polylog}(1/\epsilon))$.
• Improvement:
  • Exponential speedup in sparsity $s$ compared to [HHL09] and [CKS17] for matrices where $\|A\|_F$ is bounded.
  • Super-polynomial speedup in $1/\epsilon$ for dense linear systems (where $s \sim n$), a regime where previous quantum algorithms struggled.

4. Quantum Simulation

• Method: Constructs a block-encoding of the Hamiltonian $H$ from its classical entries and uses QSVT to approximate $e^{-iHt}$ via Jacobi-Anger expansion.
• Complexity: $O(\log(sn) \cdot \text{polylog}(1/\epsilon))$.
• Improvement: If $\|H\|_F$ is bounded, the method achieves exponential improvement in sparsity $s$ compared to standard sparse-access simulation models. It introduces a new input model: "Classically Known Rows/Columns."

5. Ground State Preparation

• Method: Uses Quantum Imaginary Time Evolution (QITE) via block-encoding.
• Complexity: $O(\frac{\|H\|_F}{\gamma} \sqrt{\frac{1}{\Delta}} \text{polylog}(1/\epsilon))$.
• Improvement: Achieves quadratic improvement in the gap $\Delta$ and exponential improvement in other parameters compared to [DLT22] and [MST+20].

6. Quantum Data Fitting (End-to-End Application)

• Method: Solves the least-squares problem $\lambda = (F^\dagger F)^{-1}F^\dagger y$ using the block-encoded linear solver.
• Innovation: The paper proposes a method to predict unseen data directly from the quantum state without full tomography or post-selection, using a SWAP/Hadamard test to estimate $f(\tilde{x}, \lambda)$.
• Complexity: $O(\|F\|_F \log(MN) \kappa_F^2 \frac{1}{\epsilon} \text{polylog}(1/\epsilon))$.
• Improvement:
  • Super-polynomial speedup in $1/\epsilon$ compared to [WBL12].
  • Exponential speedup in the number of data points $M$ for dense data (where sparsity $s \approx M$), resolving the severe limitation of [WBL12] which scales polynomially with $M$.

4. Significance and Implications

1. Bypassing QRAM: The most significant contribution is demonstrating that quantum speedups are possible without the hardware-demanding QRAM assumption. By shifting the burden to a one-time classical pre-processing step, the approach is more feasible for near-term and early fault-tolerant devices.
2. Addressing Dequantization: The results suggest that for matrices with specific structures (bounded Frobenius norm, specific sparsity patterns), quantum algorithms can still outperform the "dequantized" classical counterparts, particularly in the dense regime and regarding error scaling.
3. Practical Applicability: The paper moves beyond abstract state preparation to end-to-end applications (specifically data fitting), showing how to extract useful predictions (regression) without collapsing the quantum state prematurely.
4. New Complexity Classes: It establishes that for dense linear systems and data fitting, quantum algorithms can achieve polylogarithmic scaling in $1/\epsilon$, a feat previously thought difficult or impossible without strong input assumptions.

Conclusion

Nhat A. Nghiem's work provides a robust framework for quantum algorithms that leverages classical knowledge of data entries to construct efficient block-encodings. This approach eliminates the need for QRAM, offers exponential improvements in error tolerance and sparsity for dense problems, and provides a practical pathway for quantum advantage in machine learning and simulation tasks on near-term hardware.