論文の概要: Optimal QRAM and improved unitary synthesis by quantum circuits with any
number of ancillary qubits
- arxiv url: http://arxiv.org/abs/2202.11302v1
- Date: Wed, 23 Feb 2022 04:19:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-24 03:59:04.829249
- Title: Optimal QRAM and improved unitary synthesis by quantum circuits with any
number of ancillary qubits
- Title(参考訳): 任意の数のアクビットを持つ量子回路による最適QRAMと一元合成の改善
- Authors: Pei Yuan, Shengyu Zhang
- Abstract要約: 我々はQRAMを実装するための量子回路を構築し、任意の数に対して深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$を持つ。
これらの境界は変換の時間空間トレードオフと見なすこともできるが、任意の整数パラメータ $m,kge 0$ および $nge 1$ に対して最適である。
- 参考スコア(独自算出の注目度): 20.270300647783003
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a cornerstone for many quantum linear algebraic and quantum machine
learning algorithms, QRAM aims to provide the transformation of
$|i\rangle|0^n\rangle \to |i\rangle|\psi_i\rangle$ for all $i\in \{0,1\}^k$ for
the given $n$-qubit states $|\psi_i\rangle$. In this paper, we construct a
quantum circuit for implementing QRAM, with depth
$O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and size $O\left(2^{n+k}\right)$ for
any given number $m$ of ancillary qubits. These bounds, which can also be
viewed as time-space tradeoff for the transformation, are optimal for any
integer parameters $m,k\ge 0$ and $n\ge 1$. Our construction induces a circuit
for the standard quantum state preparation (QSP) problem of $|0^n\rangle \to
|\psi\rangle$ for any $|\psi\rangle$, pinning down its depth complexity to
$\Theta(n+2^{n}/(n+m))$ and its size complexity to $\Theta(2^{n})$ for any $m$.
This improves results in a recent line of investigations of QSP with ancillary
qubits. Another fundamental problem, unitary synthesis, asks to implement a
general $n$-qubit unitary by a quantum circuit. Previous work shows a lower
bound of $\Omega(n+4^n/(n+m))$ and an upper bound of $O(n2^n)$ for
$m=\Omega(2^n/n)$ ancillary qubits. In this paper, we quadratically shrink this
gap by presenting a quantum circuit of depth of
$O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}\right)$.
- Abstract(参考訳): 多くの量子線形代数および量子機械学習アルゴリズムの基礎として、qramは与えられた$n$-量子ビット状態に対して$|i\rangle|0^n\rangle \to |i\rangle|\psi_i\rangle$の変換を提供することを目的としている。
本稿では,QRAMを実装するための量子回路を構築し,任意の数に対して,深さ$O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$とサイズ$O\left(2^{n+k}\right)$を付した。
これらの境界は変換の時間空間トレードオフと見なすこともできるが、任意の整数パラメータ $m,k\ge 0$ および $n\ge 1$ に対して最適である。
我々の構成は、任意の$|\psi\rangle$に対して、|0^n\rangle \to |\psi\rangle$の標準量子状態準備(QSP)問題の回路を誘導し、その深さの複雑さを$\Theta(n+2^{n}/(n+m))$と、任意の$m$に対して$\Theta(2^{n})$にピン留めする。
これにより、最近のqspの調査において、副次量子ビットを用いた結果が改善される。
もう1つの根本的な問題はユニタリ合成であり、量子回路によって一般的なn$-qubitユニタリを実装することを要求する。
これまでの研究では、$\Omega(n+4^n/(n+m))$と$O(n2^n)$ for $m=\Omega(2^n/n)$の上限が示されていた。
本稿では,このギャップを,深さ$O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}\right)$の量子回路で2次的に縮小する。
関連論文リスト
- 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) - 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) - Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。
NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文 参考訳(メタデータ) (2024-02-23T12:22:03Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳(メタデータ) (2023-05-09T20:53:27Z) - On the moments of random quantum circuits and robust quantum complexity [0.0]
我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。
局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
論文 参考訳(メタデータ) (2023-03-29T18:06:03Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - Asymptotically Optimal Circuit Depth for Quantum State Preparation and
General Unitary Synthesis [24.555887999356646]
この問題は量子アルゴリズム設計、ハミルトニアンシミュレーション、量子機械学習において基本的な重要性を持っているが、その回路深さと大きさの複雑さは、アシラリー量子ビットが利用可能である時点では未解決のままである。
本稿では,$psi_vrangle$を奥行きで作成できる$m$Acillary qubitsを用いた量子回路の効率的な構築について検討する。
我々の回路は決定論的であり、状態を準備し、正確にユニタリを実行し、アシラリー量子ビットを厳密に利用し、深さは幅広いパラメータ状態において最適である。
論文 参考訳(メタデータ) (2021-08-13T09:47:11Z) - Quantum supremacy and hardness of estimating output probabilities of
quantum circuits [0.0]
我々は、出力確率を2-Omega(nlogn)$以内に近似する非集中階層の理論的な複雑さを証明している。
この硬さは、任意の(固定された)回路の任意の開近傍に拡張され、自明なゲートを持つ回路を含むことを示す。
論文 参考訳(メタデータ) (2021-02-03T09:20:32Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳(メタデータ) (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。