論文の概要: A polynomial time and space heuristic algorithm for T-count
- arxiv url: http://arxiv.org/abs/2006.12440v3
- Date: Wed, 6 Oct 2021 18:07:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-13 04:49:52.793226
- Title: A polynomial time and space heuristic algorithm for T-count
- Title（参考訳）: T数に対する多項式時間と空間ヒューリスティックアルゴリズム
- Authors: Michele Mosca and Priyanka Mukhopadhyay
- Abstract要約: この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズム実装の物理的コストの低減に重点を置いている。
普遍ゲート集合であるクリフォード+Tゲート集合からなる量子回路によって正確に実装できるユニタリ群を考える。
- 参考スコア（独自算出の注目度）: 2.28438857884398
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This work focuses on reducing the physical cost of implementing quantum
algorithms when using the state-of-the-art fault-tolerant quantum error
correcting codes, in particular, those for which implementing the T gate
consumes vastly more resources than the other gates in the gate set. More
specifically, we consider the group of unitaries that can be exactly
implemented by a quantum circuit consisting of the Clifford+T gate set, a
universal gate set. Our primary interest is to compute a circuit for a given
$n$-qubit unitary $U$, using the minimum possible number of T gates (called the
T-count of unitary $U$). We consider the problem COUNT-T, the optimization
version of which aims to find the T-count of $U$. In its decision version the
goal is to decide if the T-count is at most some positive integer $m$. Given an
oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial
in the T-count and dimension of $U$. We give a provable classical algorithm
that solves COUNT-T (decision) in time
$O\left(N^{2(c-1)\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$ and space
$O\left(N^{2\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$, where $N=2^n$ and
$c\geq 2$. This gives a space-time trade-off for solving this problem with
variants of meet-in-the-middle techniques. We also introduce an asymptotically
faster multiplication method that shaves a factor of $N^{0.7457}$ off of the
overall complexity. Lastly, beyond our improvements to the rigorous algorithm,
we give a heuristic algorithm that outputs a T-count-optimal circuit and has
space and time complexity $\text{poly}(m,N)$, under some assumptions. While our
heuristic method still scales exponentially with the number of qubits (though
with a lower exponent, there is a large improvement by going from exponential
to polynomial scaling with $m$.
- Abstract（参考訳）: この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズムの実装の物理的コストの低減に焦点を当て、特にTゲートを実装する場合、ゲートセットの他のゲートよりもはるかに多くのリソースを消費する。
より具体的には、clifford+t ゲート集合、つまりユニバーサルゲート集合からなる量子回路によって正確に実装できるユニタリのグループを考える。
我々の一番の関心は与えられた$n$-qubitのユニタリU$の回路を、最小の可能なTゲート数(TカウントのユニタリU$)を使って計算することである。
最適化版であるCOUNT-Tは、$U$のTカウントを見つけることを目的としている。
決定版では、T カウントが正の整数 $m$ であるかどうかを決定することが目的である。
COUNT-T のオラクルが与えられると、T カウントの時間多項式における T カウント最適回路を計算でき、次元は$U$である。
我々は COUNT-T (決定) を時間 $O\left(N^{2(c-1)\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$ と space $O\left(N^{2\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$ で解く証明可能な古典的アルゴリズムを与える。
これにより、中間的手法の変種でこの問題を解決するための時空トレードオフが得られる。
また、全体的な複雑性の係数を$N^{0.7457}$にする漸近的に高速な乗法も導入する。
最後に、厳密なアルゴリズムの改善以外にも、いくつかの仮定の下で、t-count-optimal回路を出力するヒューリスティックなアルゴリズムを与え、空間と時間の複雑さを$\text{poly}(m,n)$とする。
我々のヒューリスティックな方法はまだ量子ビットの数で指数関数的にスケールする(ただし指数関数は低いが、指数関数から多項式へのスケーリングは$m$で大きく改善されている)。
関連論文リスト
- A quantum random access memory (QRAM) using a polynomial encoding of binary strings [0.0]
量子ランダムアクセスメモリ(QRAM)は量子オラクルを実現するための有望なアーキテクチャである。
我々はQRAMの新しい設計を開発し、Clifford+T回路で実装する。
我々は、Tカウントを減らし、クォービット数を同じにしながら、T深度を指数的に改善する。
論文 参考訳（メタデータ） (2024-08-28T18:39:56Z) - Lower $T$-count with faster algorithms [3.129187821625805]
低実行時間で効率的な$T$-countを提案することで、$T$-count削減問題に寄与する。
様々な量子回路において,現在最高のT$カウント還元アルゴリズムであるTODDの複雑さを大幅に改善する。
我々は,さらに複雑さの低い別のアルゴリズムを提案し,評価されたほとんどの量子回路の最先端技術よりも高いあるいは等しいT$カウントを実現する。
論文 参考訳（メタデータ） (2024-07-11T17:31:20Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - T-count and T-depth of any multi-qubit unitary [1.933681537640272]
我々はクリフォード+Tゲートセット上の任意の$n$-qubit$ngeq 1$)ユニタリ$W$2ntimes 2n$のTカウントを決定するための証明可能なアルゴリズムを設計する。
我々のアルゴリズムは、任意のマルチキュービットユニタリの(最小限の)T-深さを決定できる。
論文 参考訳（メタデータ） (2021-10-19T22:16:00Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth
optimal circuits [1.933681537640272]
我々は、ネストしたミート・イン・ザ・ミドル法を用いて、証明可能なエンフデプス・最適回路とemphT・深度・最適回路を合成するアルゴリズムを開発した。
T-深さ最適化回路を合成するために、空間と時間の複雑さを持つアルゴリズムを$Oleft(left(4n2right)lceil d/crceilright)$とする。
我々のアルゴリズムは空間と時間の複雑さを$poly(n,25.6n,d)$ (or $poly(nlog n,)
論文 参考訳（メタデータ） (2021-01-08T18:13:36Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
古典的数のリストで指定された任意の次元-$N$純量子状態を作成するための量子アルゴリズムを提案する。
我々のスキームは、$mathcalO(fracNlambda+lambdalogfracNepsilonlogNepsilon)$を使用して、Tゲートコストを$mathcalO(fracNlambda+lambdalogfracNepsilon)$に削減します。
論文 参考訳（メタデータ） (2018-12-03T18:24:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。