Fugu-MT 論文翻訳(概要): Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

論文の概要: Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

arxiv url: http://arxiv.org/abs/2508.21002v1
Date: Thu, 28 Aug 2025 17:04:18 GMT
ステータス: 翻訳完了
システム内更新日: 2025-08-29 18:12:02.524186
Title: Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Title（参考訳）: 量子数列を持つスペクトルギャップと希薄な状態形成
Authors: Almudena Carrera Vazquez, Aleksandros Sobczyk,
Abstract要約: 本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
参考スコア（独自算出の注目度）: 47.600794349481966
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Approximating the $k$-th spectral gap $\Delta_k=|\lambda_k-\lambda_{k+1}|$ and the corresponding midpoint $\mu_k=\frac{\lambda_k+\lambda_{k+1}}{2}$ of an $N\times N$ Hermitian matrix with eigenvalues $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_N$, is an important special case of the eigenproblem with numerous applications in science and engineering. In this work, we present a quantum algorithm which approximates these values up to additive error $\epsilon\Delta_k$ using a logarithmic number of qubits. Notably, in the QRAM model, its total complexity (queries and gates) is bounded by $O\left( \frac{N^2}{\epsilon^{2}\Delta_k^2}\mathrm{polylog}\left( N,\frac{1}{\Delta_k},\frac{1}{\epsilon},\frac{1}{\delta}\right)\right)$, where $\epsilon,\delta\in(0,1)$ are the accuracy and the success probability, respectively. For large gaps $\Delta_k$, this provides a speed-up against the best-known complexities of classical algorithms, namely, $O \left( N^{\omega}\mathrm{polylog} \left( N,\frac{1}{\Delta_k},\frac{1}{\epsilon}\right)\right)$, where $\omega\lesssim 2.371$ is the matrix multiplication exponent. A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold, while maintaining a quadratic complexity in $N$. In the black-box access model, we also report an $\Omega(N^2)$ query lower bound for deciding the existence of a spectral gap in a binary (albeit non-symmetric) matrix.
Abstract（参考訳）: $k$-thスペクトルギャップ $\Delta_k=|\lambda_k-\lambda_{k+1}|$と対応する中間点 $\mu_k=\frac{\lambda_k+\lambda_{k+1}}{2}$ of a $N\times N$ Hermitian matrix with eigenvalues $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_N$ は、科学や工学における多くの応用を持つ固有確率の特別な場合である。本研究では、量子ビットの対数数を用いて、これらの値を加算誤差$\epsilon\Delta_k$まで近似する量子アルゴリズムを提案する。特にQRAMモデルでは、その総複雑性(クエリとゲート)は$O\left( \frac{N^2}{\epsilon^{2}\Delta_k^2}\mathrm{polylog}\left(N,\frac{1}{\Delta_k},\frac{1}{\epsilon},\frac{1}{\delta}\right)\right)$で制限される。例えば、$O \left(N^{\omega}\mathrm{polylog} \left(N,\frac{1}{\Delta_k},\frac{1}{\epsilon}\right)\right)\right)$、$\omega\lesssim 2.371$は行列乗算指数である。この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には、N$の二次的な複雑性を維持しながら、しきい値よりも小さい固有値の数を効率的に数えることができる。ブラックボックスアクセスモデルでは、バイナリ(非対称)行列におけるスペクトルギャップの存在を決定するために、$\Omega(N^2)$クエリローバウンドを報告します。

論文の概要: Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation

関連論文リスト