論文の概要: Multi-qubit Toffoli with exponentially fewer T gates

• arxiv url: http://arxiv.org/abs/2510.07223v1
• Date: Wed, 08 Oct 2025 16:56:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.642257
• Title: Multi-qubit Toffoli with exponentially fewer T gates
• Title（参考訳）: 指数的に少ないTゲートを持つマルチキュービットトフォリ
• Authors: David Gosset, Robin Kothari, Chenyi Zhang,
• Abstract要約: 私たちは、小さな1/mathrmpoly(n)$エラーを発生させるコストで、指数関数的に少ないT$ゲートで逃げる方法を示します。 より正確には、$n$-qubit Toffoli ゲートはランダムに選択された Clifford+$T$ 回路によってダイヤモンド距離の誤差 $epsilon$ 内に実装することができる。
• 参考スコア（独自算出の注目度）: 3.5887330421214063
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Prior work of Beverland et al. has shown that any exact Clifford+$T$ implementation of the $n$-qubit Toffoli gate must use at least $n$ $T$ gates. Here we show how to get away with exponentially fewer $T$ gates, at the cost of incurring a tiny $1/\mathrm{poly}(n)$ error that can be neglected in most practical situations. More precisely, the $n$-qubit Toffoli gate can be implemented to within error $\epsilon$ in the diamond distance by a randomly chosen Clifford+$T$ circuit with at most $O(\log(1/\epsilon))$ $T$ gates. We also give a matching $\Omega(\log(1/\epsilon))$ lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use $\Omega(n)$ $T$ gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the $T$-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.
• Abstract（参考訳）: Beverlandらによる以前の研究は、$n$-qubit Toffoli ゲートの正確な Clifford+$T$ の実装は少なくとも$n$$$T$ ゲートを使用する必要があることを示した。 ここでは、最小の1/\mathrm{poly}(n)$エラーを発生させるコストで、指数関数的に少ないT$ゲートで逃げる方法を示す。 より正確には、$n$-qubit Toffoli ゲートは、ランダムに選択された Clifford+$T$ 回路によって、ダイヤモンド距離の誤差 $\epsilon$ 内に実装することができる。 また、一致した $\Omega(\log(1/\epsilon))$ lower bound が最適性を確立することを示し、偶数誤差を達成する純粋にユニタリな実装は $\Omega(n)$ $T$ gates を使わなければならないことを示す。 また、サンプリング手法を拡張して他のブール関数を実装します。 最後に、非適応パリティ決定木複雑性とそのランダム化アナログの観点から、ブール関数の$T$-countの上限と下限について述べる。

関連論文リスト

• Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem [0.0]
  最近のソロワ=キタエフの定理の改善により、任意の単一量子ゲートを$epsilon > 0$ の精度で近似するには$textO(logc[1/epsilon)$ $c > 1.44042$ の量子ゲートが必要であることが示されている。 ここでは、この質問に対する部分的な回答として、$textO(log[/epsilon] loglog[/epsilon] cdots)$ FT gates が $ の値に依存する有限集合から選択されることを示す。
  論文  参考訳（メタデータ） (2024-06-07T11:21:05Z)
• Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits [0.8411424745913132]
  n$ が 2 のパワーであるとき、多ビットユニタリ行列 $U$ は $mathcalG_n$ 上の回路で正確に表現できることを示す。 さらに、$log(n)-2$ ancillasは常に$U$の回路を構築するのに十分であることを示す。
  論文  参考訳（メタデータ） (2023-11-13T20:46:51Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  可逆論理合成のためのアルゴリズムを提案する。 写像は階数 ($2n-2$) テンソルのテンソル積と 2 倍の恒等行列のテンソル積と書くことができる。
  論文  参考訳（メタデータ） (2021-07-09T08:18:53Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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