論文の概要: T-count and T-depth of any multi-qubit unitary
- arxiv url: http://arxiv.org/abs/2110.10292v5
- Date: Thu, 9 Feb 2023 05:59:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 01:53:58.431071
- Title: T-count and T-depth of any multi-qubit unitary
- Title（参考訳）: 任意のマルチキュービットユニタリのT数とT深度
- Authors: Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay
- Abstract要約: 我々はクリフォード+Tゲートセット上の任意の$n$-qubit$ngeq 1$)ユニタリ$W$2ntimes 2n$のTカウントを決定するための証明可能なアルゴリズムを設計する。
我々のアルゴリズムは、任意のマルチキュービットユニタリの(最小限の)T-深さを決定できる。
- 参考スコア（独自算出の注目度）: 1.933681537640272
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While implementing a quantum algorithm it is crucial to reduce the quantum
resources, in order to obtain the desired computational advantage. For most
fault-tolerant quantum error-correcting codes the cost of implementing the
non-Clifford gate is the highest among all the gates in a universal
fault-tolerant gate set. In this paper we design provable algorithm to
determine T-count of any $n$-qubit ($n\geq 1$) unitary $W$ of size $2^n\times
2^n$, over the Clifford+T gate set. The space and time complexity of our
algorithm are $O\left(2^{2n}\right)$ and
$O\left(2^{2n\mathcal{T}_{\epsilon}(W)+4n}\right)$ respectively.
$\mathcal{T}_{\epsilon}(W)$ ($\epsilon$-T-count) is the (minimum possible)
T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such
that $d(U,W)\leq\epsilon$ and $\mathcal{T}(U)\leq\mathcal{T}(U')$ where $U'$ is
any exactly implementable unitary with $d(U',W)\leq\epsilon$. $d(.,.)$ is the
global phase invariant distance. Our algorithm can also be used to determine
the (minimum possible) T-depth of any multi-qubit unitary and the complexity
has exponential dependence on $n$ and $\epsilon$-T-depth. This is the first
algorithm that gives T-count or T-depth of any multi-qubit ($n\geq 1$) unitary.
For small enough $\epsilon$, we can synthesize the T-count and T-depth-optimal
circuits. Our results can be used to determine the minimum count (or depth) of
non-Clifford gates required to implement any multi-qubit unitary with a
universal gate set consisting of Clifford and non-Clifford gates like
Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such
optimal-synthesis algorithm for arbitrary multi-qubit unitaries in any
universal gate set.
- Abstract（参考訳）: 量子アルゴリズムを実装する際、望ましい計算優位性を得るためには、量子資源を減らすことが不可欠である。
ほとんどのフォールトトレラント量子誤り訂正符号において、非クリフォードゲートを実装するコストは、普遍的フォールトトレラントゲートセットのすべてのゲートの中で最高である。
本稿では,Clifford+Tゲートセット上の任意の$n$-qubit$n\geq 1$)単位の$W$2^n\times 2^n$のTカウントを決定するための証明可能なアルゴリズムを設計する。
アルゴリズムの空間と時間の複雑さは、それぞれ$O\left(2^{2n}\right)$と$O\left(2^{2n\mathcal{T}_{\epsilon}(W)+4n}\right)$である。
$\mathcal{t}_{\epsilon}(w)$ (\epsilon$-t-count) は、$d(u,w)\leq\epsilon$ および $\mathcal{t}(u)\leq\mathcal{t}(u')$ のような、正確に実装可能なユニタリの (最小) t-カウントである。
$d(.,.)$は大域位相不変距離である。
このアルゴリズムは、任意のマルチキュービットユニタリの(最小の)t深さの決定にも使用でき、複雑性は、n$と$\epsilon$-t-depthに指数関数的に依存する。
これは、任意のマルチキュービット(n\geq 1$)のTカウントまたはTディープスを与える最初のアルゴリズムである。
十分小さな$\epsilon$の場合、TカウントとT深度最適化回路を合成できる。
その結果,clifford+cs,clifford+v など,clifford および非clifford ゲートからなるユニバーサルゲートセットを備えたマルチキュービットユニタリ実装に必要な非clifford ゲートの最小数(または深さ)を決定することができる。
我々の知る限りでは、任意の普遍ゲート集合における任意のマルチ量子ビットユニタリに対する最適合成アルゴリズムは存在しなかった。
関連論文リスト
- Quantum state preparation with optimal T-count [2.1386090295255333]
任意の$n$-qubit量子状態を誤差$varepsilon$に近似するために、Tゲートがいくつ必要かを示す。
また、これは任意の対角線$n$-qubitユニタリをエラー$varepsilon$に実装するための最適なTカウントであることを示す。
論文 参考訳（メタデータ） (2024-11-07T15:29:33Z) - 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) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates [0.43123403062068827]
クリフォードゲートと$O(log n)$非クリフォードゲートで用意された量子状態を効率的に学習するアルゴリズムのペアを与える。
具体的には、$n$-qubit state $|psirangle$を少なくとも$t$非クリフォードゲートで準備するために、我々のアルゴリズムは$mathsfpoly(n,2t,1/varepsilon)$timeと$|psirangle$のコピーを使って、ほとんどのゲートで距離を追跡するために$|psirangle$を学ぶ。
論文 参考訳（メタデータ） (2023-05-22T18:49:52Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - 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) - 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) - A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズム実装の物理的コストの低減に重点を置いている。
普遍ゲート集合であるクリフォード+Tゲート集合からなる量子回路によって正確に実装できるユニタリ群を考える。
論文 参考訳（メタデータ） (2020-06-22T17:21:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。