論文の概要: Optimising quantum circuits is generally hard
- arxiv url: http://arxiv.org/abs/2310.05958v3
- Date: Mon, 12 Aug 2024 11:29:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-14 00:48:29.031883
- Title: Optimising quantum circuits is generally hard
- Title(参考訳): 量子回路の最適化は一般的に難しい
- Authors: John van de Wetering, Matt Amy,
- Abstract要約: 約普遍量子回路に対する多くのゲート最適化問題はNPハードであることが判明した。
クリフォードゲートの任意の$G$に対して、クリフォード+$G$ゲート集合上の$G$カウントを最適化するのはNPハードであることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In order for quantum computations to be done as efficiently as possible it is important to optimise the number of gates used in the underlying quantum circuits. In this paper we find that many gate optimisation problems for approximately universal quantum circuits are NP-hard. In particular, we show that optimising the T-count or T-depth in Clifford+T circuits, which are important metrics for the computational cost of executing fault-tolerant quantum computations, is NP-hard by reducing the problem to Boolean satisfiability. With a similar argument we show that optimising the number of CNOT gates or Hadamard gates in a Clifford+T circuit is also NP-hard. Again varying the same argument we also establish the hardness of optimising the number of Toffoli gates in a reversible classical circuit. We find an upper bound to the problems of T-count and Toffoli-count of $\text{NP}^{\text{NQP}}$. Finally, we also show that for any non-Clifford gate $G$ it is NP-hard to optimise the $G$-count over the Clifford+$G$ gate set, where we only have to match the target unitary within some small distance in the operator norm.
- Abstract(参考訳): 量子計算をできるだけ効率的に行うためには、基礎となる量子回路で使われるゲートの数を最適化することが重要である。
本稿では, ほぼ普遍的な量子回路におけるゲート最適化問題の多くがNPハードであることを示す。
特に、フォールトトレラントな量子計算を行う計算コストの重要な指標であるクリフォード+T回路のTカウントやTディープスを最適化することは、問題をブール適合性に還元することでNPハードであることが示されている。
同様の議論により、クリフォード+T回路におけるCNOTゲート数やアダマールゲート数の最適化もNPハードであることを示す。
同じ議論を繰り返すと、可逆古典回路におけるトフォリゲートの数を最適化する難しさも確立する。
T カウントと Toffoli カウントの問題に対する上限は $\text{NP}^{\text{NQP}}$ である。
最後に、任意のクリフォードゲート $G$ に対して NP-ハードは Clifford+$G$ ゲート集合上の$G$ カウントを最適化することを示した。
関連論文リスト
- Resource Optimized Quantum Squaring Circuit [0.7673339435080445]
量子スクアリング演算は、量子アルゴリズムの実装において有用なビルディングブロックである。
誤り訂正符号とフォールトトレラント量子ゲートを用いて、量子回路をフォールトトレラントにすることができる。
本稿では,Tカウント,CNOTカウント,Tディープス,CNOTディープス,およびKQ_T$に最適化された新しい整数スクアリングアーキテクチャを提案する。
論文 参考訳(メタデータ) (2024-06-04T01:04:01Z) - Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。
Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。
注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
論文 参考訳(メタデータ) (2024-02-22T09:20:54Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。