論文の概要: POPQC: Parallel Optimization for Quantum Circuits (Extended Version)
- arxiv url: http://arxiv.org/abs/2506.13720v1
- Date: Mon, 16 Jun 2025 17:26:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-17 17:28:49.181178
- Title: POPQC: Parallel Optimization for Quantum Circuits (Extended Version)
- Title（参考訳）: POPQC:量子回路の並列最適化(拡張版)
- Authors: Pengyu Liu, Jatin Arora, Mingkuan Xu, Umut A. Acar,
- Abstract要約: 量子プログラムや回路の最適化は、量子コンピューティングの基本的な問題である。
最近の研究は、局所最適性と呼ばれるより弱い最適性を求める新しいアプローチを提案した。
本稿では,量子回路の局所最適化のための並列アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.043850178316957
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimization of quantum programs or circuits is a fundamental problem in quantum computing and remains a major challenge. State-of-the-art quantum circuit optimizers rely on heuristics and typically require superlinear, and even exponential, time. Recent work proposed a new approach that pursues a weaker form of optimality called local optimality. Parameterized by a natural number $\Omega$, local optimality insists that each and every $\Omega$-segment of the circuit is optimal with respect to an external optimizer, called the oracle. Local optimization can be performed using only a linear number of calls to the oracle but still incurs quadratic computational overheads in addition to oracle calls. Perhaps most importantly, the algorithm is sequential. In this paper, we present a parallel algorithm for local optimization of quantum circuits. To ensure efficiency, the algorithm operates by keeping a set of fingers into the circuit and maintains the invariant that a $\Omega$-deep circuit needs to be optimized only if it contains a finger. Operating in rounds, the algorithm selects a set of fingers, optimizes in parallel the segments containing the fingers, and updates the finger set to ensure the invariant. For constant $\Omega$, we prove that the algorithm requires $O(n\lg{n})$ work and $O(r\lg{n})$ span, where $n$ is the circuit size and $r$ is the number of rounds. We prove that the optimized circuit returned by the algorithm is locally optimal in the sense that any $\Omega$-segment of the circuit is optimal with respect to the oracle.
- Abstract（参考訳）: 量子プログラムや回路の最適化は量子コンピューティングの基本的な問題であり、依然として大きな課題である。
最先端の量子回路オプティマイザはヒューリスティックに依存しており、通常は超線形で指数関数的な時間を必要とする。
最近の研究は、局所最適性と呼ばれるより弱い最適性を求める新しいアプローチを提案した。
自然数$\Omega$でパラメータ付けされた局所最適性は、回路の各$\Omega$-segmentは、オラクルと呼ばれる外部オプティマイザに関して最適であると主張する。
局所最適化は、オラクルへの線形呼び出しだけを使用して行うことができるが、それでもオラクル呼び出しに加えて2次計算オーバーヘッドを発生させる。
おそらく最も重要なのは、アルゴリズムがシーケンシャルであることだ。
本稿では,量子回路の局所最適化のための並列アルゴリズムを提案する。
効率性を確保するために、アルゴリズムは、指のセットを回路に保持し、$\Omega$-deep回路が指を含む場合にのみ最適化する必要がある不変性を維持する。
ラウンドで操作すると、アルゴリズムは指のセットを選択し、指を含むセグメントを並列に最適化し、不変性を保証するために指セットを更新します。
定数$\Omega$の場合、アルゴリズムは$O(n\lg{n})$ workと$O(r\lg{n})$ spanを必要とし、$n$は回路サイズ、$r$はラウンド数である。
アルゴリズムによって返される最適化回路は、回路の$\Omega$-segmentがオラクルに対して最適であるという意味で局所的に最適であることを示す。
関連論文リスト
- Local Optimization of Quantum Circuits (Extended Version) [2.247020913864586]
本稿では,効率性と品質保証を両立できる量子プログラムの最適化手法を提案する。
局所最適性の概念はカット・アンド・メルド回路最適化アルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2025-02-26T19:53:54Z) - Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using
the Optimized Division Algorithm [1.2183405753834562]
より少ない量子ビット数を用いる二進体上の新しい量子除算アルゴリズムを提案する。
2n$のフィールドの要素に対して、$lceil n/2 rceil - 1$ qubits を 8n2+4n-12+ 16n-8)lfloorlog(n)rfloor$ more Toffoli gates の代わりに保存できる。
論文 参考訳（メタデータ） (2023-03-12T05:00:46Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Progress towards analytically optimal angles in quantum approximate
optimisation [0.0]
量子近似最適化アルゴリズム(Quantum Approximate optimization algorithm)は、量子プロセッサ上で実行される時間可変分割演算子である。
p=1$層の最適パラメータが1自由変数に減少し、熱力学の極限で最適角度を回復することが証明された。
さらに、重なり関数の勾配の消失条件は、回路パラメータ間の線形関係を導出し、キュービット数に依存しない類似の形式を持つことを示した。
論文 参考訳（メタデータ） (2021-09-23T18:00:13Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。