論文の概要: Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs

• arxiv url: http://arxiv.org/abs/2511.14296v1
• Date: Tue, 18 Nov 2025 09:51:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-19 16:23:53.038235
• Title: Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
• Title（参考訳）: 符号化ユニタリ設計からの制約付き最適化における経験的量子アドバンテージ
• Authors: Chinonso Onah, Roman Firt, Kristel Michielsen,
• Abstract要約: ブロックごとのn-1二ビット回転を用いてW_n状態を作成するアンシラフリーで深度対応のエンコーダを提供する。 原ビットストリングサンプリングに制限された古典的ベースラインに対して,ミニマックス感のexp(Theta(n2))分離を示す。
• 参考スコア（独自算出の注目度）: 0.22940141855172033
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA), a shallow, constraint-aware ansatz that operates inside the one-hot product space of size [n]^m, where m is the number of blocks and each block is initialized with an n-qubit W_n state. We give an ancilla-free, depth-optimal encoder that prepares a W_n state using n-1 two-qubit rotations per block, and a two-local XY mixer restricted to the same block of n qubits with a constant spectral gap. Algorithmically, we wrap constant-depth sampling with a deterministic classical checker to obtain a polynomial-time hybrid quantum-classical solver (PHQC) that returns the best observed feasible solution in O(S n^2) time, where S is the number of shots. We obtain two advantages. First, when CE-QAOA fixes r >= 1 locations different from the start city, we achieve a Theta(n^r) reduction in shot complexity even against a classical sampler that draws uniformly from the feasible set. Second, against a classical baseline restricted to raw bitstring sampling, we show an exp(Theta(n^2)) separation in the minimax sense. In noiseless circuit simulations of TSP instances ranging from 4 to 10 locations from the QOPTLib benchmark library, we recover the global optimum at depth p = 1 using polynomial shot budgets and coarse parameter grids defined by the problem sizes.
• Abstract（参考訳）: ブロック数 m がブロック数であり、各ブロックが n-qubit W_n 状態で初期化される場合、[n]^m の 1 ホット積空間内で動作する浅く制約を意識したアンサッツである Constraint-Enhanced Quantum Approximate Optimization Algorithm (CE-QAOA) を導入する。 我々は、ブロック毎にn-1の2量子ビット回転を用いてW_n状態を生成するアンシラフリーの深さ最適化エンコーダと、スペクトルギャップが一定であるn量子ビットの同じブロックに制限された2局所XYミキサを与える。 アルゴリズム的には、決定論的古典チェッカーを用いて定数深度サンプリングをラップし、Sがショット数であるO(S n^2)時間で最も観測可能な解を返す多項式時間ハイブリッド量子古典解法(PHQC)を得る。 私たちは2つの利点を得た。 まず、CE-QAOA が開始都市と異なる位置を r >= 1 で固定すると、可能な集合から一様に引き出す古典的なサンプリング器に対しても、ショット複雑性の Theta(n^r) の減少が達成される。 第二に、通常のビットストリングサンプリングに制限された古典的ベースラインに対して、ミニマックスの意味でexp(Theta(n^2))分離を示す。 QOPTLibベンチマークライブラリから4～10箇所のTSPインスタンスのノイズレス回路シミュレーションにおいて、多項式ショット予算と問題サイズで定義された粗いパラメータグリッドを用いて、深さp = 1での大域的最適化を復元する。

関連論文リスト

• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。 結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
  論文  参考訳（メタデータ） (2025-08-04T16:44:53Z)
• Fast Convex Optimization with Quantum Gradient Methods [2.5094874597551913]
  雑音関数評価オラクルを用いた量子(サブ)次次推定に基づく量子アルゴリズムについて検討する。 滑らかな条件と非滑らかな条件の両方において、ゼロ階凸最適化のための最初の次元非依存的な問合せ複雑性を示す。 半定値プログラミングと固有値最適化の接続を利用して、量子ミラー降下法を用いて、半定値プログラム、線形プログラム、ゼロサムゲームを解決するための新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2025-03-21T17:58:12Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  線形微分方程式に対する量子アルゴリズムを提案する。 アルゴリズムのゲートの複雑さは、次元に依存する$mathcalO(dlog(Nd))$を示す。 アルゴリズムはOrnstein-Uhlenbeck過程、ブラウン運動、L'evy飛行に対して数値的に検証される。
  論文  参考訳（メタデータ） (2024-12-19T14:04:11Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Solving The Travelling Salesman Problem Using A Single Qubit [0.0]
  トラベルセールスマン問題(TSP)はNP-ハード組合せ最適化問題として人気がある。 本稿では,量子並列性(quantum parallelism)の原理を導出し,単一量子ビットを用いて任意のTSPを解くアルゴリズムを提案する。 我々のアルゴリズムの基盤となるフレームワークは、古典的ブラキストクロンのアプローチの量子バージョンである。
  論文  参考訳（メタデータ） (2024-07-24T12:06:37Z)
• Posiform Planting: Generating QUBO Instances for Benchmarking [2.7624021966289605]
  本稿では,任意のサイズのランダムQUBOインスタンスを既知の最適解で生成する,posform plantingと呼ばれる新しい手法を提案する。 実験では,最大5,627ドルキュービットの最適化問題の最適植込み解をサンプリングするD-Wave量子アニールの能力を実証した。
  論文  参考訳（メタデータ） (2023-08-10T21:23:41Z)
• Robust sparse IQP sampling in constant depth [3.670008893193884]
  NISQ(ノイズのある中間スケール量子)は、堅牢な量子優位性と完全なフォールトトレラント量子計算の証明のないアプローチである。 本稿では,最小限の誤差補正条件でノイズに頑健な証明可能な超多項式量子優位性を実現する手法を提案する。
  論文  参考訳（メタデータ） (2023-07-20T09:41:08Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。