論文の概要: Does qubit connectivity impact quantum circuit complexity?
- arxiv url: http://arxiv.org/abs/2211.05413v1
- Date: Thu, 10 Nov 2022 08:38:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 19:42:56.770046
- Title: Does qubit connectivity impact quantum circuit complexity?
- Title（参考訳）: 量子ビット接続は量子回路の複雑さに影響を与えるか?
- Authors: Jonathan Allcock, Pei Yuan, Shengyu Zhang
- Abstract要約: すべての$n$-qubitユニタリは、1Dチェーンのqubit接続制約下であっても$O(4n/n)$ depthと$O(4n)$ sizeの回路で実装可能であることを示す。
より一般的な接続グラフを検討し、グラフが接続されている限り、常に$O(4n)$にすることができることを示す。
- 参考スコア（独自算出の注目度）: 17.158335708748385
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Some physical implementation schemes of quantum computing -- such as those
based on superconducting qubits, quantum dots, and cold atoms -- can apply
two-qubit gates only on certain pairs of qubits. Other schemes -- such as those
based on trapped ions and photonics -- are not subject to such constraints.
These qubit connectivity constraints are commonly viewed as a disadvantage; for
example, compiling an unrestricted n-qubit quantum circuit to one with poor
qubit connectivity, such as a 1D chain, usually results in a blowup of depth by
$O(n^2)$ and size by $O(n)$. It is appealing to conjecture that this overhead
is unavoidable -- a random circuit on n qubits has $\Theta(n)$ 2-qubit gates in
each layer and a constant fraction of them act on qubits separated by distance
$\Theta(n)$.
While it is known that almost all n-qubit unitaries need quantum circuits of
$\Omega(4^n/n)$ depth and $\Omega(4^n)$ size to realize, in this paper, we show
that all $n$-qubit unitaries can be implemented by circuits of $O(4^n/n)$ depth
and $O(4^n)$ size even under 1D chain qubit connectivity constraints.
We extend this result and investigate qubit connectivity along three
directions. First, we consider more general connectivity graphs, and show that
the size can always be made $O(4^n)$ as long as the graph is connected. For
depth, we study d-dimensional grids, complete d-ary trees and expander graphs,
and show results similar to the 1D chain. Second, we consider the case when
ancillae are available. We show that, with ancillae, the depth can be made
polynomial, and the space-depth trade-off is not impaired by the qubit
connectivity constraint unless we have exponentially many ancillae. Third, we
consider special unitaries, including diagonal unitaries and quantum state
preparation, the last being a fundamental task used in many quantum algorithms
for machine learning and linear algebra problems.
- Abstract（参考訳）: 量子コンピューティングの物理的実装スキーム(超伝導量子ビット、量子ドット、低温原子など)は、特定の量子ビットにのみ2量子ゲートを適用することができる。
閉じ込められたイオンやフォトニクスに基づく他のスキームは、そのような制約を受けない。
例えば、1D鎖のような1次元の量子ビット接続に制限のないnビット量子回路をコンパイルすると、通常、深さが$O(n^2)$となり、サイズが$O(n)$になる。
n qubits 上のランダム回路は各層に$\theta(n)$ 2-qubit ゲートを持ち、それらの定数分数は距離 $\theta(n)$ によって分離された qubits に作用する。
ほぼすべてのn量子ビットユニタリは、深さ$\omega(4^n/n)$の量子回路と、サイズ$\omega(4^n)$の量子回路を必要とすることが知られているが、本論文では、1dチェーン量子ビット接続制約下でも、すべてのn$量子ビットユニタリを$o(4^n/n)$の回路で実装できることを示す。
この結果を拡張し,3方向のqubit接続について検討する。
まず、より一般的な接続グラフを検討し、グラフが接続されている限り、サイズは常に$o(4^n)$となることを示す。
深度について,d-次元格子,完全d-ary木,拡張グラフについて検討し,1D鎖に類似した結果を示す。
第2に,アシラが利用可能である場合を考える。
ancillae の場合、深さは多項式となり、空間的深さのトレードオフは指数関数的に多くの ancillae がない限り qubit 接続制約によって損なわれることはない。
第3に、対角的ユニタリや量子状態準備を含む特殊ユニタリを、機械学習や線形代数問題において多くの量子アルゴリズムで使用される基本課題として考える。
関連論文リスト
- Circuit Complexity of Sparse Quantum State Preparation [0.0]
任意の$n$-qubit $d$-sparse量子状態は、$O(fracdnlog d)$とdeep $Theta(log dn)$の量子回路で、少なくとも$O(fracndlog d )$ acillary qubitsを用いて作成できることを示す。
また、回路サイズに$Omega(fracdnlog(n + m) + log d + n)$ という下界の$Omega(fracdnlog(n + m) + log d + n)$ を設定できる。
論文 参考訳（メタデータ） (2024-06-23T15:28:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Cat-qubit-inspired gate on cos($2\theta$) qubits [77.34726150561087]
我々はKerr-cat量子ビットのノイズバイアス保存ゲートにインスパイアされた1量子ビット$Z$ゲートを導入する。
このスキームは、 qubit と ancilla qubit の間のビームスプリッターのような変換を通じて位相空間の $pi$ 回転に依存する。
論文 参考訳（メタデータ） (2023-04-04T23:06:22Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - 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) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳（メタデータ） (2022-02-23T04:19:57Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Straddling-gates problem in multipartite quantum systems [20.428960719376164]
量子回路の複雑性,結合複雑性の変種について検討する。
任意の$m$partite Schmidt decomposable状態が$m$のバインディング複雑性を持つことを示す。
論文 参考訳（メタデータ） (2021-10-13T16:28:12Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳（メタデータ） (2021-08-13T09:47:11Z) - Low-depth Quantum State Preparation [3.540171881768714]
量子コンピューティングにおける重要なサブルーチンは、$N$複素数の古典的なデータを重ね合わせの$n=lceil logNrceil$-qubit状態の振幅にロードすることである。
ここでは、古典的データを用いた量子状態準備におけるこの時空トレードオフについて検討する。
我々は、$mathcal O(n2)$の回路深さを持つ量子アルゴリズムを提案し、任意の$N$複素数を符号化する。
論文 参考訳（メタデータ） (2021-02-15T13:11:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。