論文の概要: Does qubit connectivity impact quantum circuit complexity?
- arxiv url: http://arxiv.org/abs/2211.05413v2
- Date: Fri, 1 Sep 2023 07:33:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 17:19:14.624136
- Title: Does qubit connectivity impact quantum circuit complexity?
- Title（参考訳）: 量子ビット接続は量子回路の複雑さに影響を与えるか?
- Authors: Pei Yuan, Jonathan Allcock, Shengyu Zhang
- Abstract要約: 量子コンピューティングのいくつかの物理的実装スキームは、特定の量子ビットのペアにのみ2量子ゲートを適用することができる。
本稿では、$O(4n)$ depthと$O(4n)$ sizeの量子回路により、すべての$n$-qubitユニタリ演算を実装可能であることを示す。
- 参考スコア（独自算出の注目度）: 5.908927557774895
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Some physical implementation schemes of quantum computing can apply two-qubit
gates only on certain pairs of qubits. These connectivity constraints are
commonly viewed as a significant 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)$ two-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 unitary operations need quantum
circuits of $\Omega(4^n/n)$ depth and $\Omega(4^n)$ size to realize with
all-to-all qubit connectivity, in this paper, we show that all $n$-qubit
unitary operations can be implemented by quantum circuits of $O(4^n/n)$ depth
and $O(4^n)$ size even under {1D chain} qubit connectivity constraint.
We extend this result and investigate qubit connectivity in three directions.
First, we consider more general connectivity graphs and show that the circuit
size can always be made $O(4^n)$ as long as the graph is connected. For circuit
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 ancillary qubits are available. We show that, with ancilla, the circuit
depth can be made polynomial, and the space-depth trade-off is not impaired by
connectivity constraints unless we have exponentially many ancillary qubits.
Third, we obtain nearly optimal results on special families of unitaries,
including diagonal unitaries, 2-by-2 block diagonal unitaries, and Quantum
State Preparation (QSP) unitaries, the last being a fundamental task used in
many quantum algorithms for machine learning and linear algebra.
- Abstract（参考訳）: 量子コンピューティングのいくつかの物理的実装スキームは、2量子ビットゲートを特定の量子ビットのペアにのみ適用することができる。
これらの接続制約は一般に大きなデメリットと見なされる。
例えば、制限のない$n$-qubit量子回路を1dチェーンのような量子ビット接続が不十分な回路にコンパイルすると、通常、深さが$o(n^2)$、サイズが$o(n)$になる。
このオーバーヘッドは避けられない。$n$ qubits 上のランダム回路は各層に $\Theta(n)$ 2-qubit gate を持ち、その定数は距離 $\Theta(n)$ で分離された qubit 上で作用する。
ほぼすべての$n$-qubitユニタリ演算が、全量子ビット接続で実現するためには、$\Omega(4^n/n)$ depth と $\Omega(4^n)$ size の量子回路が必要であることが知られているが、本論文では、$n$-qubitユニタリ演算は、$O(4^n/n)$ depth と $O(4^n)$ size の量子回路で実装可能であることを示す。
この結果を拡張し、キュービット接続を3方向に検討する。
まず、より一般的な接続グラフを検討し、グラフが接続されている限り、回路サイズは常に$o(4^n)$となることを示す。
回路の深さについて、d$-dimensionalグリッド、d$-ary木およびexpanderグラフの完全な研究を行い、1dチェーンと同様の結果を示す。
第二に、補助キュービットが利用可能である場合を考える。
アンシラでは回路深度を多項式とし,空間深度トレードオフは指数的に多くのアシラリー量子ビットがない限り接続制約によって損なわれないことを示す。
第3に,対角ユニタリ,2-by-2ブロック対角ユニタリ,量子状態準備(qsp)ユニタリなどの特殊ユニタリについて,ほぼ最適な結果を得た。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。