論文の概要: A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth
optimal circuits
- arxiv url: http://arxiv.org/abs/2101.03142v6
- Date: Tue, 13 Sep 2022 10:16:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-17 08:17:25.484228
- Title: A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth
optimal circuits
- Title（参考訳）: t深度最適回路合成のための(quasi-)多項時間ヒューリスティックアルゴリズム
- Authors: Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay
- Abstract要約: 我々は、ネストしたミート・イン・ザ・ミドル法を用いて、証明可能なエンフデプス・最適回路とemphT・深度・最適回路を合成するアルゴリズムを開発した。
T-深さ最適化回路を合成するために、空間と時間の複雑さを持つアルゴリズムを$Oleft(left(4n2right)lceil d/crceilright)$とする。
我々のアルゴリズムは空間と時間の複雑さを$poly(n,25.6n,d)$ (or $poly(nlog n,)
- 参考スコア（独自算出の注目度）: 1.933681537640272
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We investigate the problem of synthesizing T-depth optimal quantum circuits
over the Clifford+T gate set. First we construct a special subset of T-depth 1
unitaries, such that it is possible to express the T-depth-optimal
decomposition of any unitary as product of unitaries from this subset and a
Clifford (up to global phase). The cardinality of this subset is at most
$n\cdot 2^{5.6n}$. We use nested meet-in-the-middle (MITM) technique to develop
algorithms for synthesizing provably \emph{depth-optimal} and
\emph{T-depth-optimal} circuits for exactly implementable unitaries.
Specifically, for synthesizing T-depth-optimal circuits, we get an algorithm
with space and time complexity $O\left(\left(4^{n^2}\right)^{\lceil
d/c\rceil}\right)$ and $O\left(\left(4^{n^2}\right)^{(c-1)\lceil
d/c\rceil}\right)$ respectively, where $d$ is the minimum T-depth and $c\geq 2$
is a constant. This is much better than the complexity of the algorithm by Amy
et al.(2013), the previous best with a complexity $O\left(\left(3^n\cdot
2^{kn^2}\right)^{\lceil \frac{d}{2}\rceil}\cdot 2^{kn^2}\right)$, where $k>2.5$
is a constant. We design an even more efficient algorithm for synthesizing
T-depth-optimal circuits. The claimed efficiency and optimality depends on some
conjectures, which have been inspired from the work of Mosca and Mukhopadhyay
(2020). To the best of our knowledge, the conjectures are not related to the
previous work. Our algorithm has space and time complexity $poly(n,2^{5.6n},d)$
(or $poly(n^{\log n},2^{5.6n},d)$ under some weaker assumptions).
- Abstract（参考訳）: クリフォード+Tゲートセット上でのT深度最適量子回路の合成問題について検討する。
まず、この部分集合とクリフォード(大域位相まで)からのユニタリの積として任意のユニタリのT-深度最適分解を表現することができるように、T-深度1ユニタリの特別な部分集合を構築する。
この部分集合の濃度は、最大で$n\cdot 2^{5.6n}$である。
我々は、nested meet-in-the- middle (mitm) 技術を用いて、正確に実装可能なユニタリのために、証明可能な \emph{depth-optimal} と \emph{t-depth-optimal} 回路を合成するアルゴリズムを開発する。
具体的には、T-深さ最適化回路を合成するために、空間と時間の複雑さを持つアルゴリズムを$O\left(\left(4^{n^2}\right)^{\lceil d/c\rceil}\right)$と$O\left(\left(4^{n^2}\right)^{(c-1)\lceil d/c\rceil}\right)$と取得する。
これはAmyらによるアルゴリズムの複雑さよりもはるかに優れている。
(2013) 以前の最高値である$O\left(\left(3^n\cdot 2^{kn^2}\right)^{\lceil \frac{d}{2}\rceil}\cdot 2^{kn^2}\right)$、$k>2.5$ は定数である。
さらに効率的なT深度最適化回路の合成アルゴリズムを設計する。
主張された効率性と最適性は、Mosca と Mukhopadhyay (2020) の業績から着想を得たいくつかの予想に依存する。
私たちの知る限りでは、予想は以前の仕事とは無関係である。
我々のアルゴリズムは空間と時間の複雑さが$poly(n,2^{5.6n},d)$ (または$poly(n^{\log n},2^{5.6n},d)$ である。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - 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) - Improved quantum algorithm for A-optimal projection [4.248054546466641]
本稿では、Duan emphet al.のアルゴリズムの時間的複雑さを$(frackappa4ssqrtks epsilonsmathrmpolylog)$に補正する。
我々のアルゴリズムは、Duan emphet al.のアルゴリズムと比較して少なくとも1つのスピードアップを達成する。
論文 参考訳（メタデータ） (2020-06-10T09:31:53Z) - Statistically Efficient, Polynomial Time Algorithms for Combinatorial
Semi Bandits [3.9919781077062497]
アームの集合である$cal X の部分集合 0,1d$ 上の半帯域を考える。
この問題に対して、ESCB アルゴリズムは最小の既約値 $R(T) = cal OBig(d (ln m)2 (ln T) over Delta_min Big)$ を生成するが、計算複雑性 $cal O(|cal X|)$ を持つ。
論文 参考訳（メタデータ） (2020-02-17T21:32:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。