論文の概要: Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
- arxiv url: http://arxiv.org/abs/2610.33532v1
- Date: Sat, 24 Oct 2026 08:19:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-29 19:16:30.488312
- Title: Designing Quantum Solutions to the Closest String Problem with the Non-Variational QWOA
- Title（参考訳）: 非可変QWOAを用いた最接近弦問題に対する量子解の設計
- Abstract要約: 本稿では,最も近い文字列問題に対するエンドツーエンドの量子的実装を提案する。
我々は、そのリソース要件とソリューション増幅能力を評価する。
全てのシミュレートされた問題サイズに対して、アルゴリズムは常に最適な候補とほぼ最適候補を増幅する。
- 参考スコア（独自算出の注目度）: 5.038676923228968
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing offers promising approaches to combinatorial optimization problems whose search spaces grow exponentially with problem size. The Closest String problem belongs to this category, which seeks a string that minimizes the maximum Hamming distance to any string in a given collection of reference strings. In this work, we present an end-to-end quantum implementation of the Closest String problem using the Non-Variational Quantum Walk Optimization Algorithm (NV-QWOA), evaluating its resource requirements and solution amplification capabilities. Our automated workflow converts arbitrary problem instances into quantum circuits expressed in one- or two-qubit gates that encode candidate solutions, evaluate the objective function, and apply NV-QWOA optimisation to increase the measurement probabilities of high-quality solutions. Analytical resource estimates yield a qubit complexity of $\mathcal{O}(nm\log k)$ and a circuit depth of $\mathcal{O}(pm\log^2 n + pn\log n)$, where $n$ is the string length, $m$ is the number of reference strings, $k$ is the alphabet size, and $p$ is the number of NV-QWOA iterations. We introduce a revised prescription for the phase-separation parameter, $γ$, that depends on problem size but requires no instance-specific optimization. This prescription mitigates excessive phase wrapping modulo $2π$, which can weaken the relationship between objective values and the phases guiding the optimization dynamics. Across all simulated problem sizes, the algorithm consistently amplifies optimal and near-optimal candidates. This work provides an explicit gate-level implementation, an improved phase-scaling method, and a foundation for hardware experiments and benchmarking against classical algorithms.
- Abstract（参考訳）: 量子コンピューティングは、探索空間が問題サイズとともに指数関数的に増加する組合せ最適化問題に対する有望なアプローチを提供する。
最も近い文字列問題は、与えられた参照文字列のコレクション内の任意の文字列に対するハミング距離を最小化する文字列を求めるこのカテゴリに属する。
本研究では,NV-QWOA(Non-Variational Quantum Walk Optimization Algorithm)を用いて,NV-QWOA(Non-Variational Quantum Walk Optimization Algorithm)を用いたNV-QWOA(Non-Variational Quantum Walk Optimization Algorithm,NV-QWOA)の終端量子化法を提案する。
自動ワークフローでは、任意の問題インスタンスを1または2キュービットゲートで表現された量子回路に変換し、候補解を符号化し、目的関数を評価し、NV-QWOA最適化を適用して高品質な解の測定可能性を高める。
分析資源推定は、$\mathcal{O}(nm\log k)$と$\mathcal{O}(pm\log^2 n + pn\log n)$の量子ビット複雑さを生じるが、$n$は文字列長、$m$は参照文字列の数、$k$はアルファベットサイズ、$p$はNV-QWOA反復数である。
本稿では,問題のサイズによって異なるが,インスタンス固有の最適化を必要としない位相分離パラメータである$γ$について,修正した処方料を導入する。
この処方は過度な位相ラップ法を2π$で緩和し、目的値と最適化力学を導く位相の関係を弱めることができる。
全てのシミュレートされた問題サイズに対して、アルゴリズムは常に最適な候補とほぼ最適候補を増幅する。
この研究は、明示的なゲートレベルの実装、改良された位相スケーリング法、および古典的アルゴリズムに対するハードウェア実験とベンチマークの基礎を提供する。
関連論文リスト
- Quantum iterative approach to the Traveling Salesman Problem [0.6741942263052466]
トラベリングセールスマン問題(TSP)は、最適化における古典的なNPハード問題であり、問題の規模が大きくなるにつれて、一組の都市で最短ルートを決定することは、計算的に禁止される。
この研究は、この複雑さに対処するための代替アプローチとして量子コンピューティングを探求する。
経路コストは量子位相として符号化され、QPEはそれらを効率的に評価できる一方、振幅増幅はGrover-Longアルゴリズムによって実装され、最適経路に向けた解空間を反復的に洗練する。
論文 参考訳（メタデータ） (2026-06-10T09:21:15Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Variational quantum algorithm-preserving feasible space for solving the
uncapacitated facility location problem [3.3682090109106446]
本稿では,変分量子アルゴリズムで実現可能な空間(VQA-PFS)アンサッツを提案する。
このアンザッツは制約変数に混合演算子を適用し、非制約変数にハードウェア効率アンザッツ(HEA)を用いる。
その結果, VQA-PFSは成功確率を著しく向上し, より高速な収束を示すことがわかった。
論文 参考訳（メタデータ） (2023-12-12T01:36:49Z) - Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs [0.0]
そこで我々は, 断熱量子計算に基づく線形線形解法アルゴリズムを開発した。
このアルゴリズムは最適スケーリング$O(kappa/log$)$に改善され、$epsilon$が指数関数的に改善される。
ハミルトンシミュレーションの代わりに、より安価なランダム化されたウォーク演算子法を導入する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。
我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
論文 参考訳（メタデータ） (2023-01-31T14:33:40Z) - Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover
Problem [4.697039614904225]
量子交互演算子 ansatz (QAOA+) を用いて最小被覆(MEC)問題を解く。
数値計算の結果,アルゴリズムのレベル$p$が低い場合,高い確率で解が得られることがわかった。
また、1量子ビット回転ゲートを$R_Z$で除去することで量子回路を最適化する。
論文 参考訳（メタデータ） (2022-11-28T12:45:52Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。