論文の概要: On Query-to-Communication Lifting for Adversary Bounds
- arxiv url: http://arxiv.org/abs/2012.03415v1
- Date: Mon, 7 Dec 2020 02:10:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 21:11:36.560555
- Title: On Query-to-Communication Lifting for Adversary Bounds
- Title（参考訳）: 逆境界に対する問合せと通信の昇降について
- Authors: Anurag Anshu, Shalev Ben-David, Srijita Kundu
- Abstract要約: 古典的対向境界は,一定サイズのガジェットを用いて,ランダム化通信の複雑性を低く抑えることを示す。
また、正重量子対角線が近似次数の2乗よりも大きいことも示している。
- 参考スコア（独自算出の注目度）: 14.567067583556714
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate query-to-communication lifting theorems for models related to
the quantum adversary bounds. Our results are as follows:
1. We show that the classical adversary bound lifts to a lower bound on
randomized communication complexity with a constant-sized gadget. We also show
that the classical adversary bound is a strictly stronger lower bound technique
than the previously-lifted measure known as critical block sensitivity, making
our lifting theorem one of the strongest lifting theorems for randomized
communication complexity using a constant-sized gadget.
2. Turning to quantum models, we show a connection between lifting theorems
for quantum adversary bounds and secure 2-party quantum computation in a
certain "honest-but-curious" model. Under the assumption that such secure
2-party computation is impossible, we show that a simplified version of the
positive-weight adversary bound lifts to a quantum communication lower bound
using a constant-sized gadget. We also give an unconditional lifting theorem
which lower bounds bounded-round quantum communication protocols.
3. Finally, we give some new results in query complexity. We show that the
classical adversary and the positive-weight quantum adversary are quadratically
related. We also show that the positive-weight quantum adversary is never
larger than the square of the approximate degree. Both relations hold even for
partial functions.
- Abstract（参考訳）: 量子逆境界に関連するモデルに対する問合せ対通信昇降定理について検討する。
1) 古典的敵対的境界は, 一定の大きさのガジェットで, ランダム化通信の複雑さに対して, 低い限界まで持ち上げられることを示す。
また,従来は臨界ブロック感度 ( critical block sensitivity) として知られていた手法に比べ,古典的逆境界は厳密な下界手法であり,定サイズのガジェットを用いたランダム化通信の複雑化に対して,昇降定理が最強の昇降定理であることを示した。
2. 量子モデルに目を向けると、量子逆境界に対する昇降定理と、ある「正則」モデルにおけるセキュアな2者量子計算との間の関係を示す。
このようなセキュアな2要素計算が不可能な仮定の下では、正重対向境界の簡易版が、定数サイズのガジェットを用いて量子通信の下界へ持ち上げられることを示す。
また、境界の低い量子通信プロトコルを持つ無条件リフト定理を与える。
3. 最後に、クエリの複雑さに関する新しい結果を紹介します。
古典的逆境と正の重みを持つ量子逆境は二次的関係にあることを示す。
また、正の重みを持つ量子敵は、近似次数の平方よりも決して大きいものではないことも示している。
両方の関係は部分関数に対しても成り立つ。
関連論文リスト
- QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文 参考訳（メタデータ） (2023-09-28T13:30:20Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。
最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。
因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文 参考訳（メタデータ） (2023-07-18T13:12:55Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Commitments to Quantum States [11.217084610985674]
コミットフェーズの後、コミットした状態が送信者の視点から隠されている場合、量子メッセージへのコミットが結合される。
量子状態コミットメント(QSC)の隠蔽は、古典的なメッセージに対するコミットメントスキームによってもたらされることを示す。
量子状態へのコミットは多くの新しい暗号可能性への扉を開く。
論文 参考訳（メタデータ） (2022-10-11T04:34:36Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳（メタデータ） (2021-09-06T14:35:15Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
キリアンの4メッセージ簡潔な引数系は、標準モデルでは量子後安全であることを示す。
これにより、任意の偽の仮定から最初の量子後簡潔な論証システムが得られる。
論文 参考訳（メタデータ） (2021-03-15T05:09:17Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。
我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
論文 参考訳（メタデータ） (2018-09-25T22:39:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。