技術要約：More is Less: Haar 量子マネーおよびその他のための最適セキュリティ

1. 問題提起

本論文は、量子マネーおよびコピー保護スキームにおける根本的なセキュリティ上のギャップ、すなわち、攻撃者が既存の保有物を利用して偽造を容易にする可能性に対処している。古典暗号においては、より多くのリソース（例：より多くの紙幣）を所有していても、システムの解読にかかる計算コストが低下することはない。しかし、量子の設定では、未知の量子状態の複数のコピーを所有することが、状態推定やクローニングを補助してしまう場合がある。

具体的には、著者らは $k \to k+r$ クローニング問題を調査している。これは、「未知の量子状態 $|\psi\rangle$ の $k$ 個のコピーと、反射オラクル $C|\psi\rangle Z$ へのアクセスが与えられたとき、$k+r$ 個の有効なコピーを生成するために必要なクエリ複雑性はいくらか？」という問題である。

Aaronson と Christiano [AC12] による既存の境界（例：$\Omega(\sqrt{N/k})$）は、クローニングのクエリ複雑性が $k$ の増加に伴って低下することを示唆している。これは、暗号学的な意味で「持てる者がさらに富む（the rich get richer）」ことを意味する。つまり、紙幣を多く持っているほど、偽造が容易になるということである。本論文は、この劣化が不可避なものなのか、それとも（$k \ll N$, ここで $N=2^n$）フル状態トモグラフィーに必要な閾値以下であれば、追加のコピーを生成するコストが $k$ に依存しないような構成が存在するのかを明らかにすることを目的としている。

2. 手法

2.1 下界のフレームワーク：量子タスクのための圧縮オラクル

技術的な核心となる貢献は、Zhandry の圧縮オラクル技術 [Zha19] を、クローニングという本質的に量子的タスクに新しく適応させたことである。

• オラクルの純化と離散化: 著者らはまず、連続的な Haar ランダム分布を、ランダム関数 $f: [N] \to [M]$ によって定義される位相状態の離散分布へと還元する。これにより、オラクルを量子レジスタへと純化することが可能になる。
• フーリエ基底とマルチセット: オラクルレジスタをフーリエ基底で捉えることにより、オラクルの状態は「多重度記録テーブル」（符号付き整数のマルチセット）として表現される。
  • バランス（Balance）: マルチセット内の要素の総和（反射クエリに対して不変）。
  • 負のサイズ（Negative-size）: マルチセット内の負の要素の数。
• 進捗尺度（Progress Measures）: 著者らは、マルチセットにちょうど $\ell$ 個の負の要素を持つ状態に投影する射影演算子の集合 $\Gamma_\ell$ を定義する。
  • 初期状態（$k$ 個のコピーを持つ状態）は、負のサイズが 0 である。
  • 勝利状態（$k+r$ 個のコピーを持つ状態）は、負のサイズが少なくとも $r$ である部分空間に支持されている必要がある。
  • 単一の反射クエリは、負のサイズを最大 1 だけ増加させることができる。
• 増分（Increments）の境界: 証明では、負のサイズが $\ell-1$ である部分空間から $\ell$ である部分空間への遷移確率を境界付ける。決定的なのは、この遷移が $1/\sqrt{N}$ に関連するペナルティ因子を伴うこと、および $r$ 個のステップを蓄積すると、クエリ数 $T$ が十分に大きくない限り、成功確率が指数関数的に減少することを示す点である。

2.2 上界：倍増アルゴリズム

タイトネス（緊密性）を示すために、著者らは下界と一致するアルゴリズムを構築する。

• 状態推定: アルゴリズムは、最適な POVM（対称純粋状態 POVM）を用いて未知の状態 $|\psi\rangle$ を $k$ 個のコピーから推定し、状態 $|g\rangle$ の古典的な記述を生成する。
• 振幅増幅: 推定された状態 $|g\rangle$ を用いて、アルゴリズムは固定点振幅増幅を適用し、新しい $|\psi\rangle$ のコピーを生成する。
• 倍増戦略: アルゴリズムは「倍増」戦略を採用する。$k$ 個のコピーから始めて、$2k$ 個、$4k$ 個と生成していく。$r$ 個の追加コピーを生成するための期待クエリ複雑性は、$k+r = o(N)$ である限り、$k$ に依存せず $O(\sqrt{rN})$ であることが示される。

2.3 暗号学的帰着

クローニングの境界は、以下の 2 つの暗号プリミティブに適用される。

1. 公開鍵量子マネー: 著者らは、反射オラクル検証を用いる Haar ランダム状態マネー・スキームについて、$r$ 個の追加のノートを偽造することに対するセキュリティが、$r$ と $N$ にのみ依存し、偽造者が既に保持しているノートの数 $k$ には依存しないことを示す。
2. 量子コピー保護: [ALL+21] の枠組みを適応させ、学習不能な関数のためのコピー保護スキームを構築する。彼らは、セキュリティの二分法を証明する。すなわち、攻撃者は関数を学習するか（学習不能性の仮定を破る）、あるいは Haar ランダムなプログラム状態を正常にクローンするかである。海賊行為の障壁は、保持しているコピーの数に関わらず高いまま維持される。

3. 主要な結果

3.1 タイトなクローニング境界

本論文は、クローニングのクエリ複雑性に関するタイトな境界を確立する。$N=2^n$ とする。

• 定理 1.1 ($k \to k+1$): Haar ランダムな状態 $|\psi\rangle$ に対して、$T$ 回のクエリを行い $k+1$ 個のレジスタを出力するいかなるアルゴリズムも、以下を満たす：
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+1)} \rho_\psi] \leq O\left(\frac{T^2}{N} + \frac{k+1}{N}\right)$$
  したがって、定数成功確率を得るためには、$k = o(N)$ であるとき、$T = \Theta(\sqrt{N})$ が必要となる。$k$ 個のコピーが存在することは、漸近的にクエリコストを減少させない。

• 定理 1.3 ($k \to k+r$): $r$ 個の追加コピーを生成する場合：
  $$\mathbb{E}_{|\psi\rangle} \text{Tr}[(|\psi\rangle\langle\psi|)^{\otimes(k+r)} \rho_\psi] \leq \left( O\left(\frac{T^2}{rN} + \frac{k+r}{N}\right) \right)^r$$
  最適なクエリ複雑性は $\Theta(\sqrt{rN})$ である。注目すべきは、追加のコピーあたりのコストは $r$ が増加するにつれて減少する（バッチ生成の方が効率的である）が、最初に保持しているコピー数（$k$）が増えても、有利にはならない点である。

3.2 暗号学的意義

• 量子マネー (定理 1.5): Haar ランダムな状態と反射オラクルに基づく構成は、最適なクエリセキュリティを実現する。1 枚の追加の紙幣を偽造するには、攻撃者が 1 枚持っていようと $o(2^n)$ 枚持っていようと、$\Theta(2^{n/2})$ 回のクエリが必要であり、これは $k$ に依存しない。これにより、「More is Less」のパラドックス（より多くの資産＝より多くの紙幣を持つことが、偽造能力を高めるわけではないこと）が解決される。
• コピー保護 (定理 1.6): 提案されたコピー保護スキームのセキュリティは、学習の優位性とクローニングの優位性の和によって制限される。クローニング項 $HClone_{N,k}(T^*)$ は、$k$ に依存する乗法的損失なしに $T^2/N$ としてスケールする。したがって、保護されたプログラムの複数のコピーを所有していても、海賊行為への障壁は下がらない。

4. 重要性と主張

本論文は、Aaronson [Aar09] によって提起された、複雑性理論的ノー・クローニング定理のパラメータに関する未解決問題の解決を主張している。

• 最適性: 著者らは、Haar ランダムな状態に対して「More is Less」の性質（より多くのコピーを持っても助けにならないこと）が達成可能であり、かつ最適であることを示している。このようなシステムのセキュリティは、完全な状態トモグラフィーが可能になる地点（$k \approx N$）に達するまで、保持しているコピー数が増えても劣化しない。
• 技術的新規性: 本研究は、圧縮オラクル技術を（衝突発見のような）古典的な問題ではなく、純粋に量子的タスク（クローニング）に適用した最初期の事例の一つである。多段階の進捗尺度（マルチセット内の負の要素を追跡する手法）の開発により、$k \to k+r$ の遷移に対するタイトな境界付けが可能となった。
• 暗号学的堅牢性: クローニングの障壁が $k$ に依存しないことを証明することで、本論文は量子マネーおよびコピー保護の理論的基礎を強化し、攻撃者がかなりの初期保有量を持っている場合でも、これらのシステムが安全であり続けることを保証している。

著者らは、下界の証明は AI の支援なしに開発された一方で、一般的な $k \to k+r$ のケースに関する上界については、初期の証明スケッチに AI を利用し、その後、著者らによって検証および書き直されたことを明記している。結果は、量子ランダムオラクルモデル（QROM）における位相状態にも拡張可能であり、プレーンモデルでの効率的な構成への経路を示唆しているが、そのようなインスタンス化に対するセキュリティの確立は依然として未解決の方向であると述べている。