論文の概要: Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm

• arxiv url: http://arxiv.org/abs/2610.03655v1
• Date: Fri, 02 Oct 2026 17:34:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.5287
• Title: Breaking the cubic barrier for the inverse-free Solovay-Kitaev algorithm
• Title（参考訳）: 逆自由ソロワ・キタエフアルゴリズムの立方体障壁を破る
• Abstract要約: Solovay-Kitaevアルゴリズムは、任意のユニバーサルゲートセットを使用して、効率よくユニタリを$$$$$textpolylog (1/)$時間にコンパイルできると述べている。 最近、ブーランドとジョルジュ=ティロンは、逆数なしで任意のゲート集合を効率的にコンパイルできることを示した。
• 参考スコア（独自算出の注目度）: 2.498344981748119
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Solovay-Kitaev algorithm states that it is possible to efficiently compile unitaries to accuracy $ε$ in $\text{polylog}(1/ε)$ time using any universal gate set. While Solovay and Kitaev's initial work addressed inverse-closed gate sets, recently Bouland and Giurgicǎ-Tiron showed it is possible to efficiently compile arbitrary gate sets without inverses. However, the exponent of their compilation algorithm is high. For example the inverse-free exponent for a qubit is over $8.62$, while information theoretically it is known that an inverse-free exponent of $3$ is possible in any dimension by a result of Oszmaniec, Sawicki, and Horodecki. This leads to a natural question: can one improve the exponent in Bouland and Giurgicǎ-Tiron's algorithm? And are there any cases where the inverse-free exponent is below 3, thus surpassing existing information-theoretic arguments? To answer this question, we first show that a special case of the inverse-free compiling problem -- namely Pauli gates supplemented by an irrational rotation of a qubit - admits a highly efficient compilation algorithm with an exponent at most $\approx 2.138$. Our algorithm fuses ideas from prior algorithms of Kuperberg and Sardharwalla, Cubitt, Harrow and Linden to construct an efficient ``Pauli golf'' compilation routine. We then extend these ideas to the general inverse-free case for a qubit, where we give a compiling algorithm with exponent at most $2.988$. This result uses a novel form of approximate ``aiming'' of unitary corrections to improve the compilation efficiency. Our results give two examples of quantum compiling algorithms surpassing information-theoretic arguments, and demonstrate that there are many efficiency gains possible for inverse-free compilation.
• Abstract（参考訳）: Solovay-Kitaev のアルゴリズムは、任意の普遍ゲート集合を用いて、単体を$ε$ in $\text{polylog}(1/ε)$ time に効率的にコンパイルできると述べている。 Solovay と Kitaev の初期の研究は逆閉ゲート集合に対処したが、最近の Bouland と Giurgicz-Tiron は、逆でない任意のゲート集合を効率的にコンパイルできることを示した。 しかし,コンパイルアルゴリズムの指数は高い。 例えば、量子ビットの逆フリー指数は8.62ドルを超えているが、理論的には、Oszmaniec, Sawicki, Horodecki の結果によって任意の次元で3ドルの逆フリー指数が可能であることが知られている。 ブーランドとジョルジ・ティロンのアルゴリズムの指数を改善できるか? そして、逆自由指数が 3 より下にある場合があり、従って既存の情報理論の議論を超越するだろうか? この質問に答えるために、まず、逆フリーコンパイル問題の特別な場合、すなわち、量子ビットの不合理回転で補うパウリゲートは、指数が最大$\approx 2.138$の高効率なコンパイルアルゴリズムを持つことを示す。 我々のアルゴリズムは、Kuperberg と Sardharwalla, Cubitt, Harrow, Linden の以前のアルゴリズムからアイデアを融合させ、効率的な ``Pauli golf'' のコンパイルルーチンを構築する。 すると、これらのアイデアを量子ビットの一般逆フリーケースに拡張し、指数を持つコンパイルアルゴリズムを2.988$で提供する。 この結果は、コンパイル効率を改善するために、ユニタリ補正の'aiming'を近似した新しい形式を用いている。 本結果は,情報理論的議論を超越した量子コンパイルアルゴリズムの2つの例を示し,逆フリーコンパイルには多くの効率性があることを示した。

関連論文リスト

• Classical and Quantum Algorithms for Topological Invariants of Torus Bundles [0.42970700836450476]
  我々は非可換トーラス構造を利用して閉トーラスのスキイン代数をその対称部分代数にユニタリの根に埋め込む。 個々の展開係数の抽出は#P完全であることが証明されているが、これらの係数を非無視的な構成の分数に対して効率的に近似できる量子アルゴリズムが存在する。
  論文  参考訳（メタデータ） (2025-12-22T04:58:14Z)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  乗算演算と除算演算に最適化された量子回路を提案する。 我々のアシラフリーGF乗算回路はゲートカウントの複雑さが$O(mlog3)$である。 我々は,CNOTとToffoliゲート数の両方の削減を含む,$m$の暗号関連値に対して,実用的な利点を示す。
  論文  参考訳（メタデータ） (2025-11-25T18:43:08Z)
• Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
  本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
  論文  参考訳（メタデータ） (2025-02-13T12:04:39Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Breaking the cubic barrier in the Solovay-Kitaev algorithm [0.0]
  我々は、一般有限で逆閉生成集合がクーディットに作用するようなソロヴィ-キタエフの定理とアルゴリズムを改善する。 我々の結果はより一般的に、連結半単純実リー群を密に生成する任意の有限集合に対して成り立つ。
  論文  参考訳（メタデータ） (2023-06-22T18:35:06Z)
• 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)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm [0.8594140167290096]
  Solovay-Kitaevアルゴリズムは量子計算の基本的な結果である。 普遍ゲート集合を用いて任意のユニタリを効率的にコンパイルするアルゴリズムを提供する。 普遍性を超えたゲートセット内の構造を仮定しない最初の逆フリーなソロワ・キタエフアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-12-03T17:39:41Z)
• Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams [0.0]
  順序付き二項決定図(OBDD)は、ブール関数を表す有向非巡回グラフである。 本稿では,最小のOBDDを生成する量子アルゴリズムの存在を実証することにより,量子コンピュータのさらなる高速化が可能であることを示す。
  論文  参考訳（メタデータ） (2019-09-27T12:52:07Z)

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

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