論文の概要: Circuit Design Problems in Binary Polynomial Quantum Optimization

• arxiv url: http://arxiv.org/abs/2610.13283v1
• Date: Fri, 09 Oct 2026 09:36:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.507288
• Title: Circuit Design Problems in Binary Polynomial Quantum Optimization
• Title（参考訳）: 二項多項式量子最適化における回路設計問題
• Abstract要約: 本研究では,最浅部量子回路を所定の形状に設計する問題について検討する。 我々は,それに対応するアルゴリズム的かつ性能的手法であるTempuraと,より高速な線形問題定式化を提供する。 性能評価の結果,アルゴリズムは最先端手法よりもはるかに短い回路が得られることがわかった。
• 参考スコア（独自算出の注目度）: 0.20999222360659606
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving combinatorial optimization problems on near-term quantum computers mainly relies on their quadratic unconstrained binary formulation. Lately, binary polynomial formulations start to take the center stage, having a better scaling with respect to the number of used qubits. However, while quadratic forms are straightforward to implement on quantum circuits, polynomial forms of degree $d$ incur in circuit depth overheads, due to the lack of $d$-qubit gates, for $d\geq 3$, on current hardware. In this paper, we study the problem of designing the shallowest quantum circuit for a given polynomial form. We formulate it as a classical binary linear problem and we prove the \textsf{NP}-completeness of a variant of it. On the algorithmic side, we offer a scalable and performant heuristic method to tackle it, Tempura, as well as faster binary linear problem formulations, which offer computational feasibility while sacrificing optimality. Our performance evaluation shows that the algorithms yield far shorter circuits than the state-of-the-art approaches, and Tempura is mostly comparable with them in terms of runtime.
• Abstract（参考訳）: 短期量子コンピュータにおける組合せ最適化問題の解法は、主に2次的制約なしのバイナリ定式化に依存する。 最近、二項多項式の定式化は中心的な段階に入り始め、使用したキュービットの数に関してより優れたスケーリングを持つ。 しかし、二次形式は量子回路上では簡単に実装できるが、現在のハードウェアでは$d\geq 3$に対して$d$-qubitゲートが存在しないため、回路深さのオーバーヘッドに$d$の多項式形式が生じる。 本稿では,与えられた多項式形式に対して,最も浅い量子回路を設計する問題について検討する。 古典的二項線型問題として定式化し、その変項の \textsf{NP}-完全性を証明する。 アルゴリズムの面では、それに取り組むためのスケーラブルで高性能なヒューリスティックな方法であるTempuraと、より高速な線形問題定式化を提供し、最適性を犠牲にして計算可能性を提供する。 性能評価の結果,提案アルゴリズムは最先端手法よりもはるかに短い回路を出力し,Tempuraは実行時とほぼ同等であることがわかった。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  そこで本研究では,NP-Complete問題から準拘束的二項最適化問題への抽象化問題を符号化する手法を開発した。 QUBOの定式化により、QuantumやDigital Annealersといった新しいコンピューティングアーキテクチャを活用することができる。 論証や議論の実施における古典的問題の正しさと適用性を証明するために,実験を行った。
  論文  参考訳（メタデータ） (2024-09-09T11:29:46Z)
• 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)
• Optimizing Variational Circuits for Higher-Order Binary Optimization [2.578242050187029]
  本稿では,ハミルトニアンを2量子ゲートのみを含む実装可能な回路に符号化する新しい手法を提案する。 本手法は,回路深度の観点から明らかな利得を示すとともに,技術状況と比較することで評価する。
  論文  参考訳（メタデータ） (2023-07-31T15:27:06Z)
• Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing [0.22730034612794422]
  本稿では,量子アダマール積を用いて計算した非線形関数の近似に基づくアルゴリズムを開発する。 我々の設定では、形が双対数因子である場合にのみ量子スピードアップが証明できる。 我々は、最近IBMの量子デバイスに導入された動的回路機能を利用して、量子アダマール製品回路証明の平均深度を下げる。
  論文  参考訳（メタデータ） (2023-04-20T15:22:08Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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