論文の概要: How Not to Build Microcrypt

• arxiv url: http://arxiv.org/abs/2609.30253v1
• Date: Thu, 24 Sep 2026 17:58:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:10.21082
• Title: How Not to Build Microcrypt
• Title（参考訳）: マイクロ暗号を作らない方法
• Abstract要約: 量子暗号の鍵となる課題は、量子一方向性と擬似ランダム性を(量子計算可能な)一方向関数を使わずに構築することである。 PRS と PRU の既存アーキテクチャの多くは,一方通行の関数を避けるために明示的に導入されたもので,実際は一方通行の関数の存在を暗示している。
• 参考スコア（独自算出の注目度）: 7.682244137762325
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A key challenge in quantum cryptography is to build quantum one-wayness and pseudorandomness without the use of (quantum computable) one-way functions. So far, this has turned out to be a difficult task, with only a few proposed candidates that are not directly built from one-way functions. Even within these few proposed candidates, we have lacked the techniques to analyze when proposed constructions may inadvertently yield one-way functions. In this work, we introduce efficient NP-aided shadow tomography of quantum states. We prove that collections of {\em computable} pure states can be learned via efficient NP-aided shadow tomography, where we say that a state is computable if the amplitude and phase on any computational basis term can be classically efficiently computed given the description of an efficient preparation circuit for the state. We also give new algorithms for NP-aided learning of unitaries given polynomially many queries to the unitary. By building on this, we show that many existing architectures for PRS and PRU, including some that were explicitly introduced for the purposes of avoiding one-way functions (e.g., Hamiltonian Phase States, Bostanci et. al., TQC 2025), actually do imply the existence of one-way functions or imply \(\NP\) hardness. We hope that these no-go results will inform future investigations into building PRS and PRUs from assumptions that are plausibly outside the complexity class NP.
• Abstract（参考訳）: 量子暗号における鍵となる課題は、量子一方向性と擬似ランダム性を(量子計算可能)一方向関数を使わずに構築することである。 今のところ、これは難しい作業であり、一方的な関数から直接構築されていない候補はごくわずかである。 これらの数少ない提案候補においても,提案手法が必然的に一方向関数を生成できるかどうかを解析する手法が欠如している。 本研究では,量子状態の効率的なNP援用シャドウトモグラフィを提案する。 計算可能な純状態の集合はNP支援の効率的なシャドウトモグラフィにより学習できることを証明し、任意の計算基底項の振幅と位相が、その状態の効率的な準備回路の記述から古典的に計算可能であれば、状態は計算可能であると述べる。 また,NP支援型ユニタリ学習のための新しいアルゴリズムを提案し,各ユニタリに対して多項式的に多数のクエリを付与する。 このことから, PRS と PRU の既存アーキテクチャの多くは,一方通行関数(例えば,ハミルトン位相状態,ボスタンチ等,TQC 2025)の回避のために明示的に導入されたもので,実際は一方通行関数の存在を示唆するものであるか,あるいは(\NP\) 硬さを暗示するものである。 これらのノーゴーの結果が、複雑性クラスNPの外側にある仮定から、PSRとPRUを構築するための将来の調査となることを願っている。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• Random Unitaries in Constant (Quantum) Time [0.8516351290711953]
  我々は、量子計算のよく研究されたモデルにおいて、ユニタリ設計とPRUを効率的に構築できることを示す。 その結果、単体設計とPRUは以前考えられていたよりもはるかに弱い回路モデルで構築可能であることが示された。
  論文  参考訳（メタデータ） (2025-08-15T14:04:49Z)
• Quantum Algorithms for Compositional Text Processing [1.3654846342364308]
  本稿では、最近提案された自然言語用DisCoCircフレームワークに注目し、量子適応QDisCoCircを提案する。 これはAI解釈可能なレンダリングに対する構成的アプローチによって動機付けられている。 テキスト類似性のモデルネイティブな原始演算に対しては、フォールトトレラントな量子コンピュータのための量子アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-08-12T11:21:40Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  安定猫量子ビットの既存システムに動機づけられたビットフリップ誤差のみに影響されるバイアスノイズ量子ビットを考察する。 現実的なノイズモデルでは、位相フリップは無視できないが、Pauli-Twirling近似では、ベンチマークが最大106ドルのゲートを含む回路の正しさを確認できる。
  論文  参考訳（メタデータ） (2023-05-03T11:27:50Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
  特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。 量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。 提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
  論文  参考訳（メタデータ） (2021-06-06T13:15:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。