  Noisy linear problems have been studied in various science and engineering
disciplines. A class of "hard" noisy linear problems can be formulated as
follows: Given a matrix $\hat{A}$ and a vector $\mathbf{b}$ constructed using a
finite set of samples, a hidden vector or structure involved in $\mathbf{b}$ is
obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x}
\approx \mathbf{b} + \boldsymbol\eta$, where $\boldsymbol\eta$ is a noise
vector that cannot be identified. For solving such a noisy linear problem, we
consider a quantum algorithm based on a divide-and-conquer strategy, wherein a
large core process is divided into smaller subprocesses. The algorithm
appropriately reduces both the computational complexities and size of a quantum
sample. More specifically, if a quantum computer can access a particular
reduced form of the quantum samples, polynomial quantum-sample and time
complexities are achieved in the main computation. The size of a quantum sample
and its executing system can be reduced, e.g., from exponential to
sub-exponential with respect to the problem length, which is better than other
results we are aware. We analyse the noise model conditions for such a quantum
advantage, and show when the divide-and-conquer strategy can be beneficial for
quantum noisy linear problems.
