論文の概要: Improved Synthesis of Toffoli-Hadamard Circuits
- arxiv url: http://arxiv.org/abs/2305.11305v1
- Date: Thu, 18 May 2023 21:02:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 17:19:44.092590
- Title: Improved Synthesis of Toffoli-Hadamard Circuits
- Title（参考訳）: toffoli-hadamard回路の改良
- Authors: Matthew Amy, Andrew N. Glaudell, Sarah Meng Li, Neil J. Ross
- Abstract要約: Kliuchnikovが2013年にClifford+$T$回路に対して導入した手法はトフォリ・ハダード回路に容易に適用可能であることを示す。
また、同様のコスト改善の代替合成法を提案するが、その応用は3キュービット未満の回路に限られる。
- 参考スコア（独自算出の注目度）: 1.7205106391379026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The matrices that can be exactly represented by a circuit over the
Toffoli-Hadamard gate set are the orthogonal matrices of the form $M/
\sqrt{2}{}^k$, where $M$ is an integer matrix and $k$ is a nonnegative integer.
The exact synthesis problem for this gate set is the problem of constructing a
circuit for a given such matrix. Existing methods produce circuits consisting
of $O(2^n \log(n)k)$ gates, where $n$ is the dimension of the matrix. In this
paper, we provide two improved synthesis methods. First, we show that a
technique introduced by Kliuchnikov in 2013 for Clifford+$T$ circuits can be
straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity
of the synthesized circuit from $O(2^n \log(n)k)$ to $O(n^2 \log(n)k)$. Then,
we present an alternative synthesis method of similarly improved cost, but
whose application is restricted to circuits on no more than three qubits. Our
results also apply to orthogonal matrices over the dyadic fractions, which
correspond to circuits using the 2-qubit gate $H\otimes H$, rather than the
usual single-qubit Hadamard gate $H$.
- Abstract（参考訳）: Toffoli-Hadamard ゲート集合上の回路で正確に表現できる行列は、$M/ \sqrt{2}{}^k$ という形の直交行列であり、$M$ は整数行列であり、$k$ は非負の整数である。
このゲート集合の正確な合成問題は、与えられた行列に対する回路を構成する問題である。
既存の方法は、$O(2^n \log(n)k)$ゲートからなる回路を生成し、$n$は行列の次元である。
本稿では,2つの改良された合成法を提案する。
まず、クリフニコフが2013年に導入したclifford+$t$回路の手法をトッフォリ・ハダマール回路に容易に適用でき、合成回路の複雑さを$o(2^n \log(n)k)$から$o(n^2 \log(n)k)$に低減できることを示した。
次に、同様のコスト改善の代替合成法を提案するが、その適用範囲は3量子ビット以下の回路に限られる。
また,dyadic分数上の直交行列についても適用し,通常の1量子ゲート$h$ではなく2量子ビットゲート$h\otimes h$を用いた回路に対応する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Minimum Synthesis Cost of CNOT Circuits [0.0]
我々は合成においてCNOTゲートを分類する新しい方法を用いて、$O(nomega)$時間で計算可能な厳密な下界を求める。
フレームワークを適用すると、$n$サイクル回路の3(n-1)$ゲート合成が最適であることが証明され、それらの構造についての洞察が得られる。
論文 参考訳（メタデータ） (2024-08-15T03:09:53Z) - Incompressibility and spectral gaps of random circuits [2.359282907257055]
可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。
ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
論文 参考訳（メタデータ） (2024-06-11T17:23:16Z) - S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for
unstructured sparse matrices [0.0]
Fast Approximate BLock-Lazyアルゴリズム(FABLE)は、任意の$Ntimes N$高密度行列を量子回路にブロックエンコードする手法である。
スパース行列を効率的に符号化するFABLEの2つの修正について述べる。
論文 参考訳（メタデータ） (2024-01-08T20:57:16Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Fast Differentiable Matrix Square Root [65.67315418971688]
微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。
前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。
もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
論文 参考訳（メタデータ） (2022-01-21T12:18:06Z) - An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
可逆論理合成のためのアルゴリズムを提案する。
写像は階数 ($2n-2$) テンソルのテンソル積と 2 倍の恒等行列のテンソル積と書くことができる。
論文 参考訳（メタデータ） (2021-07-09T08:18:53Z) - Efficient reconstruction of depth three circuits with top fan-in two [0.0]
有限体上のブラックボックス再構成問題を解くための効率的なランダム化アルゴリズムを開発した。
この回路クラスの最初のブラックボックス再構成アルゴリズムは、$log |mathbbF|$で実行されます。
論文 参考訳（メタデータ） (2021-03-12T18:19:34Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。