論文の概要: Reassessing the computational advantage of quantum-controlled ordering
of gates
- arxiv url: http://arxiv.org/abs/2102.11293v1
- Date: Mon, 22 Feb 2021 19:00:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-10 05:44:49.533765
- Title: Reassessing the computational advantage of quantum-controlled ordering
of gates
- Title（参考訳）: ゲートの量子制御順序付けの計算的利点の再評価
- Authors: Martin J. Renner, \v{C}aslav Brukner
- Abstract要約: 量子計算において、不確定因果構造は、2つのユニタリゲートが各ゲートへの1つの呼び出しで通勤するか反通勤するかを決定する。
本研究では,この利点が期待よりも小さいことを示す。
我々は、$O(nlog(n))$クエリで唯一知られている特定のFPPを解決する因果アルゴリズムと、$O(nsqrtn)$クエリですべてのFPPを解決する因果アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Research on indefinite causal structures is a rapidly evolving field that has
a potential not only to make a radical revision of the classical understanding
of space-time but also to achieve enhanced functionalities of quantum
information processing. For example, it is known that indefinite causal
structures provide exponential advantage in communication complexity when
compared to causal protocols. In quantum computation, such structures can
decide whether two unitary gates commute or anticommute with a single call to
each gate, which is impossible with conventional (causal) quantum algorithms. A
generalization of this effect to $n$ unitary gates, originally introduced in M.
Ara\'ujo et al., Phys. Rev. Lett. 113, 250402 (2014) and often called Fourier
promise problem (FPP), can be solved with the quantum-$n$-switch and a single
call to each gate, while the best known causal algorithm so far calls $O(n^2)$
gates. In this work, we show that this advantage is smaller than expected. In
fact, we present a causal algorithm that solves the only known specific FPP
with $O(n \log(n))$ queries and a causal algorithm that solves every FPP with
$O(n\sqrt{n})$ queries. Besides the interest in such algorithms on their own,
our results limit the expected advantage of indefinite causal structures for
these problems.
- Abstract（参考訳）: 不定因果構造の研究は急速に発展する分野であり、時空の古典的理解を過激に修正するだけでなく、量子情報処理の高機能化を実現する可能性を秘めている。
例えば、不定因果構造は因果プロトコルと比較して通信の複雑さに指数関数的な利点をもたらすことが知られている。
量子計算において、そのような構造は2つのユニタリゲートが各ゲートへの単一の呼び出しで可換か反共動かを決定できるが、これは従来の量子アルゴリズムでは不可能である。
この効果を M. Ara\'ujo et al., Phys に導入した$n$ユニタリゲートに一般化する。
Rev. Lett.
113, 250402 (2014) とよく呼ばれるフーリエ約束問題 (FPP) は、量子=$$switch と各ゲートへの1回の呼び出しで解けるが、最もよく知られている因果アルゴリズムは$O(n^2)$ gates である。
本研究では,この利点が期待よりも小さいことを示す。
実際、既知の特定のFPPを$O(n \log(n))$クエリで解く因果アルゴリズムと、$O(n\sqrt{n})$クエリですべてのFPPを解く因果アルゴリズムを提案する。
このようなアルゴリズムへの関心に加えて、これらの問題に対する不確定因果構造が期待できる優位性を制限する。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。
最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。
因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文 参考訳（メタデータ） (2023-07-18T13:12:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Experimentally feasible computational advantage from quantum
superposition of gate orders [0.0]
通常の量子アルゴリズムでは、ゲートは系の固定順序で適用される。
不定因果構造の導入により、この制約を緩和し、追加の量子状態でゲートの順序を制御することができる。
この量子制御されたゲートの順序付けは、ゲートを固定順序で適用する最適なアルゴリズムに関してブラックボックスユニタリの性質を決定する際のクエリの複雑さを低減することが知られている。
論文 参考訳（メタデータ） (2021-12-29T13:36:27Z) - Approaching the theoretical limit in quantum gate decomposition [0.0]
本稿では,CNOT$ゲート数を持つ1量子および2量子ビットの量子ゲートを用いて,一般量子プログラムを分解する新しい数値計算手法を提案する。
本手法は, 既設計量子回路における単一量子ビット回転ゲートに関するパラメータの逐次最適化に基づく。
論文 参考訳（メタデータ） (2021-09-14T15:36:22Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Quantum Logarithmic Space and Post-selection [0.4588028371034406]
ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。
我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。
また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
論文 参考訳（メタデータ） (2021-05-06T14:02:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。