論文の概要: Optimising T-count is NP-hard
- arxiv url: http://arxiv.org/abs/2310.05958v2
- Date: Tue, 17 Oct 2023 10:04:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 20:07:59.183928
- Title: Optimising T-count is NP-hard
- Title(参考訳): Tカウントの最適化はNPハードである
- Authors: John van de Wetering, Matt Amy
- Abstract要約: 可逆的古典回路において、$textNPtextNQP$のTカウント問題に対する上限を求める。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this short note we show that Boolean satisfiability reduces to finding the
optimal number of T gates of a quantum circuit, and hence that optimising
T-count is NP-hard. We show that the same argument extends to optimising the
number of Toffoli gates in a reversible classical circuit, and we furthermore
find an upper bound to the T-count problem of $\text{NP}^{\text{NQP}}$.
- Abstract(参考訳): 本稿では,ブール整合性は量子回路のTゲートの最適個数が減少し,Tカウントの最適化がNPハードであることを示す。
同じ引数が可逆古典回路における toffoli ゲートの数を最適化するために拡張されることを示し、さらに$\text{np}^{\text{nqp}}$ の t-項問題に対する上限を見つける。
関連論文リスト
- Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。
Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。
注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
論文 参考訳(メタデータ) (2024-02-22T09:20:54Z) - BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。
近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
論文 参考訳(メタデータ) (2024-01-08T14:59:48Z) - Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。
入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。
我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
論文 参考訳(メタデータ) (2022-10-13T09:01:58Z) - T-count optimization of approximate quantum Fourier transform [0.0]
Toffoliゲートと量子加算器を用いた誤りO(varepsilon)に近似した新しいn-qubit QFT回路を提案する。
論文 参考訳(メタデータ) (2022-03-15T09:13:51Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳(メタデータ) (2022-02-10T18:59:52Z) - 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 polynomial time and space heuristic algorithm for T-count [2.28438857884398]
この研究は、最先端のフォールトトレラントな量子エラー訂正符号を使用する場合の量子アルゴリズム実装の物理的コストの低減に重点を置いている。
普遍ゲート集合であるクリフォード+Tゲート集合からなる量子回路によって正確に実装できるユニタリ群を考える。
論文 参考訳(メタデータ) (2020-06-22T17:21:41Z) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳(メタデータ) (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。