Solving systems of linear equations is a fundamental problem, but it can be
computationally intensive for classical algorithms in high dimensions. Existing
quantum algorithms can achieve exponential speedups for the quantum linear
system problem (QLSP) in terms of the problem dimension, but even such a
theoretical advantage is bottlenecked by the condition number of the
coefficient matrix. In this work, we propose a new quantum algorithm for QLSP
inspired by the classical proximal point algorithm (PPA). Our proposed method
can be viewed as a meta-algorithm that allows inverting a modified matrix via
an existing \texttt{QLSP\_solver}, thereby directly approximating the solution
vector instead of approximating the inverse of the coefficient matrix. By
carefully choosing the step size $\eta$, the proposed algorithm can effectively
precondition the linear system to mitigate the dependence on condition numbers
that hindered the applicability of previous approaches.

通过选择合适的步长 η，本文提出了一种新的量子算法，对量子线性系统问题（QLSP）进行求解，解决了之前方法中依赖条件数的问题。

基于近端点算法的量子线性系统问题的催化剂框架

A Catalyst Framework for the Quantum Linear System Problem via the  Proximal Point Algorithm

In this paper, we revisit the smooth and strongly-convex-strongly-concave
minimax optimization problem. Zhang et al. (2021) and Ibrahim et al. (2020)
established the lower bound $\Omega\left(\sqrt{\kappa_x\kappa_y} \log
\frac{1}{\epsilon}\right)$ on the number of gradient evaluations required to
find an $\epsilon$-accurate solution, where $\kappa_x$ and $\kappa_y$ are
condition numbers for the strong convexity and strong concavity assumptions.
However, the existing state-of-the-art methods do not match this lower bound:
algorithms of Lin et al. (2020) and Wang and Li (2020) have gradient evaluation
complexity $\mathcal{O}\left(
\sqrt{\kappa_x\kappa_y}\log^3\frac{1}{\epsilon}\right)$ and $\mathcal{O}\left(
\sqrt{\kappa_x\kappa_y}\log^3 (\kappa_x\kappa_y)\log\frac{1}{\epsilon}\right)$,
respectively. We fix this fundamental issue by providing the first algorithm
with $\mathcal{O}\left(\sqrt{\kappa_x\kappa_y}\log\frac{1}{\epsilon}\right)$
gradient evaluation complexity. We design our algorithm in three steps: (i) we
reformulate the original problem as a minimization problem via the pointwise
conjugate function; (ii) we apply a specific variant of the proximal point
algorithm to the reformulated problem; (iii) we compute the proximal operator
inexactly using the optimal algorithm for operator norm reduction in monotone
inclusions.

通过重新定义问题为最小化问题，应用特定变体的近端点算法和使用最佳算法计算不准确的近端算子，我们将最小极小化优化问题的梯度计算复杂度降至 O (sqrt (kappax*kappay)*log (1/epsilon))

平滑与强凸强凹极小 - 极大优化的首个最优算法

The First Optimal Algorithm for Smooth and  Strongly-Convex-Strongly-Concave Minimax Optimization

This paper studies minimax optimization problems $\min_x \max_y f(x,y)$,
where $f(x,y)$ is $m_x$-strongly convex with respect to $x$, $m_y$-strongly
concave with respect to $y$ and $(L_x,L_{xy},L_y)$-smooth. Zhang et al.
provided the following lower bound of the gradient complexity for any
first-order method: $\Omega\Bigl(\sqrt{\frac{L_x}{m_x}+\frac{L_{xy}^2}{m_x
m_y}+\frac{L_y}{m_y}}\ln(1/\epsilon)\Bigr).$ This paper proposes a new
algorithm with gradient complexity upper bound
$\tilde{O}\Bigl(\sqrt{\frac{L_x}{m_x}+\frac{L\cdot L_{xy}}{m_x
m_y}+\frac{L_y}{m_y}}\ln\left(1/\epsilon\right)\Bigr),$ where
$L=\max\{L_x,L_{xy},L_y\}$. This improves over the best known upper bound
$\tilde{O}\left(\sqrt{\frac{L^2}{m_x m_y}} \ln^3\left(1/\epsilon\right)\right)$
by Lin et al. Our bound achieves linear convergence rate and tighter dependency
on condition numbers, especially when $L_{xy}\ll L$ (i.e., when the interaction
between $x$ and $y$ is weak). Via reduction, our new bound also implies
improved bounds for strongly convex-concave and convex-concave minimax
optimization problems. When $f$ is quadratic, we can further improve the upper
bound, which matches the lower bound up to a small sub-polynomial factor.

该研究针对广泛应用于深度学习等领域的极小极大优化问题提出了新算法，利用加速方法获得极小极大问题的优秀渐进收敛速度和更紧密的条件数依赖性.

凸凹最小化极小化优化的改进算法

Improved Algorithms for Convex-Concave Minimax Optimization

This paper resolves a longstanding open question pertaining to the design of
near-optimal first-order algorithms for smooth and
strongly-convex-strongly-concave minimax problems. Current state-of-the-art
first-order algorithms find an approximate Nash equilibrium using
$\tilde{O}(\kappa_{\mathbf x}+\kappa_{\mathbf y})$ or
$\tilde{O}(\min\{\kappa_{\mathbf x}\sqrt{\kappa_{\mathbf y}},
\sqrt{\kappa_{\mathbf x}}\kappa_{\mathbf y}\})$ gradient evaluations, where
$\kappa_{\mathbf x}$ and $\kappa_{\mathbf y}$ are the condition numbers for the
strong-convexity and strong-concavity assumptions. A gap still remains between
these results and the best existing lower bound
$\tilde{\Omega}(\sqrt{\kappa_{\mathbf x}\kappa_{\mathbf y}})$. This paper
presents the first algorithm with $\tilde{O}(\sqrt{\kappa_{\mathbf
x}\kappa_{\mathbf y}})$ gradient complexity, matching the lower bound up to
logarithmic factors. Our algorithm is designed based on an accelerated proximal
point method and an accelerated solver for minimax proximal steps. It can be
easily extended to the settings of strongly-convex-concave, convex-concave,
nonconvex-strongly-concave, and nonconvex-concave functions. This paper also
presents algorithms that match or outperform all existing methods in these
settings in terms of gradient complexity, up to logarithmic factors.

本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法，其梯度复杂度为 O（kappa_x kappa_y^0.5），匹配了已有的最优下界，可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。