Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Quantum solvability of noisy linear problems by divide-and-conquer
  strategy   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.

22
The categories of this paper are: chao-dyn
37
The categories of this paper are: supr-con
12
The categories of this paper are: nucl-th
35
The categories of this paper are: mtrl-th
24
The categories of this paper are: dg-ga
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
30
The categories of this paper are: q-alg
8
The categories of this paper are: hep-ex
27
The categories of this paper are: comp-gas
16
The categories of this paper are: stat
2
The categories of this paper are: math
11
The categories of this paper are: hep-lat
34
The categories of this paper are: chem-ph
6
The categories of this paper are: astro-ph
18
The categories of this paper are: econ