マックスカット問題のフロッケアディアバティックアルゴリズムのベンチマーク
Etienne Granet1, Henrik Dreyer2
1Quantinuum, Leopoldstrasse 180, 80804, Munich, Germany. etienne.granet@quantinuum.com.
Scientific reports
|August 30, 2025
まとめ
フロッケのアディアバティック・エボリューションは 最適化問題のより効率的な量子コンピューティングアプローチを提供します. この方法はゲート数を大幅に削減し,量子コンピュータのマックスカットのような問題に対する最適な解決策を可能にします.
科学分野:
- 量子力学
- コンピュータ科学
- 最適化アルゴリズム
背景:
- 量子力学のアディアバティック定理は,基本的な状態にあるシステムは,ハミルトンのゆっくりとした変化の下で基本状態のままであると述べている.
- アディアバティック量子計算原理は複雑な問題を解くことができますが,トロッターステップスケーリングにより,デジタル量子コンピュータではしばしば大きなゲートカウントが必要です.
研究 の 目的:
- デジタル量子コンピュータでアディアバティックダイナミクスを効率的に実装するための新しいアプローチ,Floquetのアディアバティック進化を調査する.
- 古典的な最適化問題,特にマックスカット問題の解決のためのフロケアアディアバティック進化の有効性を実証する.
主な方法:
- 提案されたフロッケアディアバティック進化,アディアバティックダイナミクスのための固定された,有限なトロッターステップを使用する.
- この方法の有効性を数値的に証明するために,マトリックス・プロダクト・ステート・シミュレーションを使用した.
- マックスカット問題で3つの規則的なグラフでアプローチをテストしました.
主要な成果:
- フロッケのアディアバティック進化は,連続時間のアディアバティック進化と比較して,ゲート数を数桁大幅に減らす.
- 数値シミュレーションは,ランタイムと結合寸法が低い3正規グラフでマックスカット問題の最適解を示します.
- 資源の見積もりは 量子コンピュータが この問題に対する クラシックな解決法を上回る可能性を示唆しています
結論:
- フロッケのアディアバティック進化は,アディアバティック量子計算のための計算効率の良い代替案を提示します.
- この方法は近期量子装置のマックスカットのような 難しい最適化問題を解くのに 有望です
関連する概念動画
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
100
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
100
01:09Turbulent Flow: Problem Solving
183
Carbonation is a process used to dissolve carbon dioxide gas in a liquid, commonly used in the production of carbonated beverages. Achieving efficient carbonation requires careful control of temperature, pressure, and flow conditions. By adjusting these parameters, carbonation efficiency can be maximized, producing a higher concentration of CO2 in the liquid.
Temperature is a key factor in CO2 solubility. In this case, the CO2 gas and the liquid are cooled to 20°C. Lower temperatures...
Temperature is a key factor in CO2 solubility. In this case, the CO2 gas and the liquid are cooled to 20°C. Lower temperatures...
183
01:21Heuristics
148
Heuristics are problem-solving strategies that use mental shortcuts to simplify decision-making. Unlike algorithms, which must be followed precisely to achieve a correct result, heuristics offer a general problem-solving framework. They save time and energy but can sometimes lead to less rational decisions.
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
148
01:20Maxwell-Boltzmann Distribution: Problem Solving
1.7K
Individual molecules in a gas move in random directions, but a gas containing numerous molecules has a predictable distribution of molecular speeds, which is known as the Maxwell-Boltzmann distribution, f(v).
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
This distribution function f(v) is defined by saying that the expected number N (v1,v2) of particles with speeds between v1 and v2 is given by
1.7K
01:24Laminar Flow: Problem Solving
250
Laminar flow occurs when a fluid moves smoothly in parallel layers with minimal mixing and turbulence. In fluid mechanics, ensuring laminar flow within a pipe is essential for precise control of flow characteristics, especially in engineering applications. The key factor in determining whether flow remains laminar is the Reynolds number, a dimensionless quantity that depends on the fluid's velocity, density, viscosity, and the pipe's diameter. A Reynolds number of 2100 or lower...
250
01:18Uniform Depth Channel Flow: Problem Solving
124
To calculate the flow rate for a trapezoidal channel, first, identify the bottom width, side slope, and flow depth of the channel. The cross-sectional area (A) corresponding to the depth of flow (y), channel bottom width (B), and side slope (θ) is determined by:Next, calculate the wetted perimeter, which includes the bottom width and the sloped side lengths in contact with the water. Using the values of the cross-sectional area and the wetted perimeter, determine the hydraulic radius by...
124