論文の概要: Uncloneable Quantum Advice
- arxiv url: http://arxiv.org/abs/2309.05155v1
- Date: Sun, 10 Sep 2023 22:09:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-12 14:17:16.394795
- Title: Uncloneable Quantum Advice
- Title(参考訳): 不可解な量子アドバイス
- Authors: Anne Broadbent, Martti Karvonen, S\'ebastien Lord
- Abstract要約: 計算を可能とした複雑性理論ツールの研究を通して、初めて、未知の量子不連続性を示す。
ここでは、無条件の量子アドバイスを許容する公約問題の存在と、無条件のアドバイスを持つ言語の存在を示す。
- 参考スコア(独自算出の注目度): 1.1970409518725493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The famous no-cloning principle has been shown recently to enable a number of
uncloneable functionalities. Here we address for the first time unkeyed quantum
uncloneablity, via the study of a complexity-theoretic tool that enables a
computation, but that is natively unkeyed: quantum advice. Remarkably, this is
an application of the no-cloning principle in a context where the quantum
states of interest are not chosen by a random process. We show the
unconditional existence of promise problems admitting uncloneable quantum
advice, and the existence of languages with uncloneable advice, assuming the
feasibility of quantum copy-protecting certain functions. Along the way, we
note that state complexity classes, introduced by Rosenthal and Yuen (ITCS
2022) - which concern the computational difficulty of synthesizing sequences of
quantum states - can be naturally generalized to obtain state cloning
complexity classes. We make initial observations on these classes, notably
obtaining a result analogous to the existence of undecidable problems.
Our proof technique establishes the existence of ingenerable sequences of
finite bit strings - essentially meaning that they cannot be generated by any
uniform circuit family. We then prove a generic result showing that the
difficulty of accomplishing a computational task on uniformly random inputs
implies its difficulty on any fixed, ingenerable sequence. We use this result
to derandomize quantum cryptographic games that relate to cloning, and then
incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable
advice. Applying this two-step process to a monogamy-of-entanglement game
yields a promise problem with uncloneable advice, and applying it to the
quantum copy-protection of pseudorandom functions with super-logarithmic output
lengths yields a language with uncloneable advice.
- Abstract(参考訳): 有名なノークローニングの原理は、最近多くの不可避な機能を可能にするために示されてきた。
ここでは、計算を可能にする複雑性-理論的なツールの研究を通して、初めてunkeyed quantum uncloneablityに対処します。
これは、興味のある量子状態がランダムなプロセスによって選択されない文脈における非閉原理の応用である。
量子的助言を許容する約束問題の無条件存在と、特定の関数の量子的コピー保護の可能性を仮定して、不可解なアドバイスを持つ言語の存在を示す。
その過程で、量子状態列の計算困難を懸念するRosenhal and Yuen (ITCS 2022) によって導入された状態複雑性クラスが自然に一般化され、状態クローニング複雑性クラスが得られることに留意する。
これらのクラスについて最初の観察を行い、特に決定不能な問題の存在と類似した結果を得た。
この証明手法は有限ビット文字列の帰納的列の存在を立証するものであり、本質的には一様回路族では生成できないことを意味する。
次に、一様ランダムな入力における計算タスクの達成が困難であることは、任意の固定化不可能なシーケンスにおいてその困難を示唆していることを示す。
この結果を用いて、クローンに関連する量子暗号ゲームをデランドマイズし、クンドゥとタンの結果(arXiv 2022)を組み込んで非クローン的なアドバイスを得る。
この二段階の過程を一夫一婦制ゲームに適用すると、必然的なアドバイスを伴う約束問題となり、超対数出力長を持つ疑似ランダム関数の量子コピー保護に適用すると、不可解なアドバイスを持つ言語が得られる。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Commitments from Quantum One-Wayness [0.0]
本研究は、片方向関数の自然な量子緩和である片方向状態発生器を研究する。
根本的な問題は、このタイプの量子ワンウェイネスが量子暗号を実現するのに十分であるかどうかである。
我々は、純粋な状態出力を持つ一方通行状態生成器が量子ビットのコミットメントを暗示し、セキュアなマルチパーティ計算を行うことを証明した。
論文 参考訳(メタデータ) (2023-10-17T18:48:22Z) - 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) - Quantum Pseudoentanglement [4.3053817709507]
エンタングルメント(英: Entanglement)は、古典計算におけるランダムネスに類似した量子資源である。
カット毎に$log n$ に近い絡み合いエントロピーを持つ擬アンタングル状態の構成を与える。
本稿では, マトリックス製品状態試験, エンタングルメント蒸留, およびAdS/CFT対応の複雑さへの応用について論じる。
論文 参考訳(メタデータ) (2022-11-01T21:04:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳(メタデータ) (2021-07-05T17:45:41Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳(メタデータ) (2021-03-16T20:54:12Z) - Characterization of quantum states based on creation complexity [0.0]
量子状態の生成複雑性は、基本初期状態から生成するために必要な基本ゲートの最小数である。
完全に一般の量子状態が指数関数的に困難であること(生成の複雑さを判断するためには、指数関数的に量子ビットの個数と指数関数的にスケールするいくつかのステップが要求される)を示す。
次に、生成複雑性の大きい大規模な量子状態が、任意の候補量子状態が与えられたとき、そのクラスに属するか否かを任意に高い成功確率で決定するための効率的な係数サンプリング手順を設計できるような共通の係数特徴を持つことを示す。
論文 参考訳(メタデータ) (2020-04-28T21:12:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。