論文の概要: Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps
- arxiv url: http://arxiv.org/abs/2604.21274v1
- Date: Thu, 23 Apr 2026 04:36:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-24 14:40:06.30407
- Title: Random Access Codes: Explicit Constructions, Optimality, and Classical-Quantum Gaps
- Title（参考訳）: ランダムアクセスコード:明示的な構成、最適性、古典的な量子ギャップ
- Authors: Ruho Kondo, Yuki Sato, Hiroshi Yano, Yota Maeda, Kosuke Ito, Naoki Yamamoto,
- Abstract要約: 我々は,平均値と最悪値の両方の基準の下で,古典的な$(L,k)$-RACの構成的フレームワークを開発する。
これらの最適符号は$(L,L-1)$-QRACを誘導し、復号成功確率の予想上限に達することを示す。
- 参考スコア（独自算出の注目度）: 1.3033126970138174
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A random access code (RAC) encodes an $L$-bit string into a $k$-bit $(L>k)$ message from which any designated source bit can be recovered with high probability. Its quantum counterpart, a quantum random access code (QRAC), replaces the $k$-bit message with $k$ qubits. While upper bounds on the decoding success probability have long been studied in both classical and quantum settings, explicit constructions of optimal codes are known only in special cases, even for classical RACs. In this paper, we develop a constructive framework for classical $(L,k)$-RACs under both average- and worst-case criteria. We show that optimal code design reduces to selecting $2^k$ points in $\{0,1\}^L$ and $[0,1]^L$ for the average- and worst-case criteria, respectively, so as to minimize a distance-like objective. This characterization yields explicit constructions for general $(L,k)$. For $k=L-1$, we further obtain closed-form optimal encoders and decoders for both criteria, and show that the resulting classical $(L,L-1)$-RACs attain the corresponding proved upper bounds. We also show that these optimal classical codes induce $(L,L-1)$-QRACs that attain a conjectured upper bound on the decoding success probability. Numerical optimization suggests little difference between RACs and QRACs in the average-case setting, but a potentially large classical-quantum gap in the worst-case nonasymptotic regime.
- Abstract（参考訳）: ランダムアクセスコード(RAC)は、$L$-bit文字列を$k$-bit $(L>k)$メッセージにエンコードする。
量子ランダムアクセスコード(QRAC)は、$k$-bitメッセージを$k$ qubitsに置き換える。
復号成功確率の上限は、古典的および量子的設定の両方で長い間研究されてきたが、最適符号の明示的な構成は、古典的RACにおいても特別な場合にのみ知られている。
本稿では,古典的な$(L,k)$-RACを平均値と最悪の値の両方で構築可能なフレームワークを開発する。
最適符号設計は,平均値と最低値の基準に対して,$${0,1\}^L$と$[0,1]^L$の2^k$ポイントを選択することで,距離のような目的を最小化できることを示す。
この特徴づけは、一般$(L,k)$に対して明示的な構成をもたらす。
さらに、$k=L-1$の場合、両方の基準に対して閉形式最適エンコーダとデコーダを取得し、その結果の古典的な$(L,L-1)$-RACsが対応する証明された上限に達することを示す。
また、これらの最適古典符号は、復号成功確率の予想上限に達した$(L,L-1)$-QRACを誘導することを示した。
数値最適化は、平均ケース設定におけるRACとQRACの差はほとんどないが、最悪のケース漸近状態における古典的量子ギャップが潜在的に大きいことを示唆している。
関連論文リスト
- Optimal Quantum $(r,δ)$-Locally Repairable Codes via Classical Ones [52.3857155901121]
LRC(Local repairable codes)は、大規模分散およびクラウドストレージシステムにおいて、データ損失を軽減する上で重要な役割を果たす。
本稿では、一般最適$(r,delta)$-LRCに対する統一的な分解定理を確立する。
フレキシブルパラメータを持つ最適量子$(r,delta)$-LRCの3つの無限族を構成する。
論文 参考訳（メタデータ） (2025-07-24T08:21:20Z) - Quantum One-Time Memories from Stateless Hardware, Random Access Codes, and Simple Nonconvex Optimization [0.0]
本稿では,古典的アクセス可能なステートレスハードウェアを用いたワンタイムメモリ(OTM)の構築について述べる。
上記のアプローチとは異なり、我々のアプローチは2つの古典ビットを符号化するためにQRAC(quantum random access code)を利用する。
ハードウェアに対する多くの古典的なクエリに対して、健全さを証明します。
論文 参考訳（メタデータ） (2025-01-07T22:29:33Z) - Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。
提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
論文 参考訳（メタデータ） (2024-05-30T21:36:12Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Biased Random Access Codes [0.0]
ランダムアクセスコード(英: random access code、RAC)は、送信者が受信機によって復号される短いメッセージにランダムメッセージを符号化する通信タスクである。
本稿では,古典的戦略と量子的戦略の両方に対して最適性能を数値的に評価するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-16T18:53:25Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum Random Access Codes for Boolean Functions [0.05076419064097732]
我々は、古典的(f$-RAC)および量子(f$-QRAC)エンコーディングによる$f$-randomアクセスコードのためのプロトコルを研究、提供する。
プロトコルの成功確率はブール関数$f$のエンフォネーズ安定性によって特徴づけられる。
論文 参考訳（メタデータ） (2020-11-12T17:48:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。