Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

秘密量子信号処理

勇人 西窪

Published Mar 1, 2024• 0 citations
OpenAlex

Abstract

量子計算は古典計算と比較して,特定の問題について優位に計算を行うことができることが様々な研究で立証されており,現在注目を集めている.中でも,量子信号処理(QSP) というLow とChuang によって提案された,1 量子ビットの回転行列の回転角を変換する技術は一際注目が集められている.この技術は元来,核磁気共鳴における信号強度を増幅するための手法であったが,量子情報科学における重要な問題の一つであるハミルトニアンシミュレーションに対して最適なアルゴリズムを提供することなども証明されており,その応用可能性について広く研究が行われている.具体的にはMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算などがある.古典計算では1 ビットメモリ上で対称ブール関数を計算することは不可能であることが知られており,この結果は量子計算の優位性を示していることが分かる.この計算プロトコルにおいて,QSP は1 量子ビットメモリで計算するための核を担っている. 本研究ではQSP について暗号理論の観点からその応用可能性について検討し,その結果,新たな応用として秘密量子信号処理(PQSP) を提案する.PQSP は秘密同時通信(PSM) と呼ばれる計算モデルにおいてQSP を実行するプロトコルである.具体的には,それぞれがQSP の回転角に関する秘密の入力をもつn 人の参加者が,一人の独立した評価者を通じてQSP の出力ユニタリ行列を計算するというものである.PQSP では評価者に対して各参加者が持つ秘密の入力が,出力から洩れる情報以上に洩れることがないことを保証しつつ,参加者から評価者へ送信されるメッセージの通信量が無限の場合は完全に正しい計算結果を得ることができる.ただし,通信量を有限とするためには各参加者の送信するメッセージを有限精度で表現する必要があり,その際にはPQSP が最終的に出力する行列に誤りが発生する.よって,本研究ではこの精度と誤りのトレードオフについての評価も行う. PQSP の応用例として,先述のMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算が挙げられる.本研究では,Maslov らの手法で使用されているQSP をPQSP と置換することで,1 量子ビットメモリ上で対称ブール関数を計算することができるという優位性はそのままに,PSM モデルにおいて評価者に対して出力情報以上を洩らさずに計算が可能であることを示した. また,本研究ではCosentino らによって提案された1 量子ビットプロトコルに対してPQSPで用いる秘匿化手法を適用することで,PSM モデルにおいて1 量子ビットメモリ上で任意のブール関数を計算することが可能なプロトコルである秘密1 量子ビットプログラム(P1QP)を提案する.P1QP はPQSP の応用で計算可能な対称ブール関数より大きな関数クラスに属する任意のブール関数を計算可能であることから,より一般的であるといえる.

Related papers

幾何学的なパズルに対する物理的ゼロ知識証明

Kyosuke Hatsugai

ゼロ知識証明は,ある問題の解答を知る証明者が,解答そのものを教えることなく,問題に解答が存在することを検証者に納得させるプロトコルである.また,カードベース暗号は,計算機の代わりにカードや封筒といった物理的な道具を用いて秘密計算を実現する暗号プロトコルである.カードベース暗号ではゼロ知識証明を実現するプロトコルも考案されており,これらは特に物理的ゼロ知識証明と呼ばれている. 物理的ゼロ知識証明が考案されたパズルの個数について,数値が条件に含まれるパズルに比べて図形の性質が問題や解答の条件に含まれるパズルは少ない.そこで,本研究では幾何学的な特徴を持つパズルを対象に物理的ゼロ知識証明を提案する. 本研究では,二次元図形と三次元図形の双方で幾何学的な特徴をカードで表現するために,時間ロボー問題に対する物理的ゼロ知識証明の改良を行い,天体ショーに対する物理的ゼロ知識証明を新たに提案した.時間ドロボー問題はn個のキューブで構成されたパズルである.先行研究である上田・西村のプロトコルはカードのみで実装できるが,証明者が解答を知らなくても検証者が証明に納得する健全性誤りが生じる問題がある.卒業研究では,カードの他にハサミと立方体を用いることで健全性誤りのないプロトコルを考案した.そこで本研究では,上田・西村の設定と同じくカードのみで実装でき,かつ健全性誤りのないプロトコルを提案する.天体ショーは与えられたブロックを点対称な図形に分割するパズルである.天体ショーに対する物理的ゼロ知識証明では,時間ドロボー問題に対する研究で考案した,立方体を削減する操作を利用することで,解答である分割後の図形の形状を検証者に教えることなく,各図形が点対称であることを証明する.

•Mar 24, 2023•0 citations

Private Quantum Signal Processing

Akinori Kawachi, Yuto NISHIKUBO

Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 6, 2025•2 citations

確率的対数領域計算による確率行列のスペクトルギャップ増幅

Kensuke Suzuki

近年,量子計算機の研究開発が盛んに行われており,量子計算量クラスに関する理論的な研究も活発に行われている.量子計算機は古典計算機に比べ高速に計算できることが期待されており,すでに実装可能な量子計算機がスーパーコンピュータを上回る性能に達しているという研究結果も存在する[3].しかし現在実装可能な量子計算機は古典計算機に比べ扱えるビット数が少ないため,量子領域計算クラスに関する困難性を明らかにすることは重要な課題となっている. また量子計算機はすべての問題において古典計算機より高速に計算できるわけではない.量子ビットは古典ビットに比べ少ない量で多くの情報を保持することが可能だが,保持した情報を一つずつ取り出すといった操作は得意ではない.こういった性質から,量子計算機では行列演算など複数の情報を用いた演算を古典計算機より少ないステップで行い,その結果を出力するという問題に強く,実際に行列に関する様々な問題の量子アルゴリズムが考案されている.こういった量子計算量クラスに関する様々な研究成果が出る中で,古典計算量クラスとの関係性を明らかにすることは量子計算機を活用するうえで重要な指標となる.現在行列問題における古典計算量クラスと量子計算量クラスの違いとして,扱えることのできる行列の種類や,近似を行う際の精度といったことが予想されている. このような背景より,古典における領域複雑性と行列問題の精度の観点から,Doron らの研究[6] に注目した.Doron らは確率行列の第二固有値を判定する問題について,逆多項式の精度を要求する場合はBPL 完全であることを示した.しかし彼らの研究において,より簡単な問題である定数精度を要求する第二固有値問題がどれほど困難かについては議論されておらず,定数精度と逆多項式精度の第二固有値問題における困難性が同等かは不明である.そこで本研究では逆多項式精度の第二固有値問題を定数精度に確率的対数領域計算で帰着させることで,定数精度と逆多項式精度の第二固有値問題が確率的対数領域計算において同等の困難性を持つことを示そうと試みた.結果として確率的対数領域計算が可能な状況では,定数精度の第二固有値問題が一部の逆多項式精度の問題より困難であることを示した.

•Mar 1, 2023•0 citations

最適な量子測定に基づく量子ニューラルネットワーク分類器の性能評価

優作 山田

最近の量子コンピュータの研究は,ノイズの影響を受けやすい,NISQデバイスと呼ばれる量子コンピュータの活用が研究されている.NISQデバイスは量子ニューラルネットワーク(以下,QNN)による,古典-量子アルゴリズムで応用されている.このアルゴリズムは教師あり分類問題において,4つのステップで構成されている.(1)古典データを量子状態に埋め込む回路を初期状態に作用させる.(2)パラメータに依存する回路を適用する.(3)Z基底測定で測定をする.(4)古典最適化アルゴリズムを用いて,最適なパラメータを見つけ,量子回路を更新する.その後,更新したパラメータでテストデータを分類する. 先行研究では,アルゴリズムのステップ(1)と(2)を重要視し,ヒューリスティックに回路を設計して量子優位性を主張している.先行研究で提案されていることは,2量子ビット間のエンタングルメント回路を取り入れることと,古典ニューラルネットワークのように,量子回路を繰り返すことである.このことによって量子優位性が得られ,教師あり分類問題に関して,本質的で重要な要素であることを主張している. 本研究は,先行研究の主張を受けて,次の2つのことを主張する.1つ目は,ヒューリスティックに構成されたエンタングルメントや回路の繰り返しは,分類問題において本質的でないこと.2つ目は,分類問題において本質的に重要なことは,任意の軸回りにおける測定の最適化をすることである.提案方法は,測定により得る古典データを分析する前に,量子状態に対して個別に任意の軸回りにパラメータ化された単一回転ゲートを作用させ,最適な測定を行うことである. 本研究で使用したデータは,人工的な2値分類データと実データのIris Data Setである.これらのデータにおいて,先行研究では,分類できないと主張されているような単純な回路でも,測定最適化をすることで分類精度が95%を超える結果が得られた.また,測定最適化した回路は,調査した全ての回路に対して分類精度が向上することが確認でき,最大で7%の分類精度から91%の分類精度への向上が見られた.さらに,測定最適化を行うことで,実データであるIris Data Setに対しても,先行研究のQNN分類器の分類精度と同等の分類精度93%の結果が得られた.測定最適化は,単一の量子ビットにしか作用されず,そのパラメータ数も量子ビットに対して線形にしか増えない.以上の結果と利点により,QNNの分類問題において本質的に重要なことは,測定の最適化であると主張する.

•Mar 24, 2023•0 citations

A Numerical Study on a Noisy Order of Channels and Information Quantities

Kai Ou

盗聴通信路符号化などの情報理論的安全性に基づく暗号理論においては,盗聴者が用いる通信路は,正規受信者が用いる通信路よりノイズが多いことが仮定される.しかし,盗聴者の通信路を正確に特定できない場合,想定される通信路の中で一番ノイズが少ない通信路を盗聴者が用いるものとして安全性を確保する必要がある.そのため,通信路を比較するための順序を導入する必要があり,これまでもless noisy order (Korner-Marton, 1975) など,通信路に関する様々な順序が研究されてきた.中でも,二つの通信路W, V が与えられたとき,一方の通信路V が他方の通信路Wにさらにノイズを付加した通信路となる関係W > V (degraded order) は統計的にも重要である(Blackwell-Sherman-Stein, 1951). 本論文では,通信路のノイズに関する順序(degraded order) について二つ観点で数値的な研究を行った.一つは通信路の順序と情報量(相互情報量および相対レニーエントロピー)の関係についての研究であり,もう一つは,順序を判定する効率的なアルゴリズムの開発である. 最初に,通信路の順序と相互情報量および相対レニーエントロピーの関係について数値実験による研究を行った.通信路W と通信路の入力アルファベット上の確率分布P が与えられると,相互情報量I(P;W) が計算できる.相互情報量の単調性(データ処理不等式)より,二つの通信路W, V が順序関係W > V を満たす(V はW よりノイズが多い)ならば,すべての入力分布Pについて,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つ.本研究では,この命題の逆が成立するかどうかを調べるため,数値実験により,3 入力3 出力の通信路を多数調べることで反例を探した.その結果,反例として,非常に多くの入力分布P について,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つが,順序関係W > V を満たさない例を多数見つけた.相対レニーエントロピーについても同様の単調性が成り立つことが知られている.この場合も同様に,単調性の逆の命題が成立しない多数の反例を見つけた. 次に,二つの通信路W, V が任意に与えられたとき,順序関係W > V が満たされるかどうかを判定する一般的なアルゴリズムの開発を行った.本論文では,通信路W に付加的なノイズU が加わる状況を考え,U を変えて行くことでW とU の合成通信路が通信路V に一致するかどうかを最急降下法により調べた.その際,コスト関数として確率遷移行列の成分の二乗和を用いた.また,付加するノイズU も確率遷移行列である必要がるため,U の行列成分は非負かつ行和は1 でなければならない.本論文では,U を指数分布族により表現することで,確率遷移行列の制約条件を満たしながらコスト関数を最小化するアルゴリズムを開発した.

•Sep 28, 2012•0 citations

盗聴通信路符号化における特性関数を用いた安全性評価について

雄喜 森

現在最もよく使われているRSA暗号や楕円曲線暗号は,計算量的安全性に基づく公開鍵暗号系に分類される汎用量子コンピュータが実現した場合,Shor のアルゴリズム(1994)により素因数分解問題や離散対数問題が多項式時間で解かれてしまうため,RSA 暗号等の安全性が崩れることが理論的に知られている.近年,汎用量子コンピュータの開発研究において,量子デバイスのブレイクスルーが起こっている.今後20年程度の間に汎用量子コンピュータが実現される見込みが高い.Wyner の盗聴通信路符号化によれば,正規受信者と盗聴者が用いる通信路のノイズ差が利用出来る状況においては,盗聴者に対する完全秘匿を確保しながら正規受信者に誤りなくメッセージや秘密鍵を伝送する符号化が可能になる.理論的には,符号長を大きくして安全な符号を生成出来ることが分かっている.ただし,生成された符号が「実際に安全かどうか」を確認するための手段が理論的に与えられていない. 本研究では,情報理論的安全性に基づく暗号系の一つである盗聴通信路符号化をコセット符号化を用いて実現させるために,特性関数を用いて安全性評価を行うという方法を提案する. 本研究ではファネス型不等式を用いて,盗聴者の持つ情報と一様分布の1-normを経由したエントロピーによる安全性評価を行う方法を提案した.さらに,確率分布の1-normを具体的に計算することは一般に困難なので,確率分布の1-normを直接計算する代わりに,多変数特性関数の2-normで強安全性を用いた安全性評価を行う方法を提案する.その結果,計算量の大幅な削減を行うことができるということがわかり,数値実験によりその優位性を示した.

•Feb 23, 2018•0 citations
量子計算は古典計算と比較して,特定の問題について優位に計算を行うことができることが様々な研究で立証されており,現在注目を集めている.中でも,量子信号処理(QSP) というLow とChuang によって提案された,1 量子ビットの回転行列の回転角を変換する技術は一際注目が集められている.この技術は元来,核磁気共鳴における信号強度を増幅するための手法であったが,量子情報科学における重要な問題の一つであるハミルトニアンシミュレーションに対して最適なアルゴリズムを提供することなども証明されており,その応用可能性について広く研究が行われている.具体的にはMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算などがある.古典計算では1 ビットメモリ上で対称ブール関数を計算することは不可能であることが知られており,この結果は量子計算の優位性を示していることが分かる.この計算プロトコルにおいて,QSP は1 量子ビットメモリで計算するための核を担っている. 本研究ではQSP について暗号理論の観点からその応用可能性について検討し,その結果,新たな応用として秘密量子信号処理(PQSP) を提案する.PQSP は秘密同時通信(PSM) と呼ばれる計算モデルにおいてQSP を実行するプロトコルである.具体的には,それぞれがQSP の回転角に関する秘密の入力をもつn 人の参加者が,一人の独立した評価者を通じてQSP の出力ユニタリ行列を計算するというものである.PQSP では評価者に対して各参加者が持つ秘密の入力が,出力から洩れる情報以上に洩れることがないことを保証しつつ,参加者から評価者へ送信されるメッセージの通信量が無限の場合は完全に正しい計算結果を得ることができる.ただし,通信量を有限とするためには各参加者の送信するメッセージを有限精度で表現する必要があり,その際にはPQSP が最終的に出力する行列に誤りが発生する.よって,本研究ではこの精度と誤りのトレードオフについての評価も行う. PQSP の応用例として,先述のMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算が挙げられる.本研究では,Maslov らの手法で使用されているQSP をPQSP と置換することで,1 量子ビットメモリ上で対称ブール関数を計算することができるという優位性はそのままに,PSM モデルにおいて評価者に対して出力情報以上を洩らさずに計算が可能であることを示した. また,本研究ではCosentino らによって提案された1 量子ビットプロトコルに対してPQSPで用いる秘匿化手法を適用することで,PSM モデルにおいて1 量子ビットメモリ上で任意のブール関数を計算することが可能なプロトコルである秘密1 量子ビットプログラム(P1QP)を提案する.P1QP はPQSP の応用で計算可能な対称ブール関数より大きな関数クラスに属する任意のブール関数を計算可能であることから,より一般的であるといえる.
ゼロ知識証明は,ある問題の解答を知る証明者が,解答そのものを教えることなく,問題に解答が存在することを検証者に納得させるプロトコルである.また,カードベース暗号は,計算機の代わりにカードや封筒といった物理的な道具を用いて秘密計算を実現する暗号プロトコルである.カードベース暗号ではゼロ知識証明を実現するプロトコルも考案されており,これらは特に物理的ゼロ知識証明と呼ばれている. 物理的ゼロ知識証明が考案されたパズルの個数について,数値が条件に含まれるパズルに比べて図形の性質が問題や解答の条件に含まれるパズルは少ない.そこで,本研究では幾何学的な特徴を持つパズルを対象に物理的ゼロ知識証明を提案する. 本研究では,二次元図形と三次元図形の双方で幾何学的な特徴をカードで表現するために,時間ロボー問題に対する物理的ゼロ知識証明の改良を行い,天体ショーに対する物理的ゼロ知識証明を新たに提案した.時間ドロボー問題はn個のキューブで構成されたパズルである.先行研究である上田・西村のプロトコルはカードのみで実装できるが,証明者が解答を知らなくても検証者が証明に納得する健全性誤りが生じる問題がある.卒業研究では,カードの他にハサミと立方体を用いることで健全性誤りのないプロトコルを考案した.そこで本研究では,上田・西村の設定と同じくカードのみで実装でき,かつ健全性誤りのないプロトコルを提案する.天体ショーは与えられたブロックを点対称な図形に分割するパズルである.天体ショーに対する物理的ゼロ知識証明では,時間ドロボー問題に対する研究で考案した,立方体を削減する操作を利用することで,解答である分割後の図形の形状を検証者に教えることなく,各図形が点対称であることを証明する.
Quantum signal processing (QSP), which is a general technique for construction of 1-qubit rotation operators, is a strong framework for quantum algorithm design. We consider a scenario of information-theoretically secure computation for QSP: n parties who have private angle parameters make the evaluator perform the QSP from the sum of their angles in a privacy-preserving manner through noninteractive communication. In this scenario, we construct a private simultaneous messages (PSM) protocol for QSP, named Private QSP (PQSP). As an application, we construct an efficient PSM protocol for symmetric Boolean functions with an evaluator of 1-qubit workspace by adapting PQSP to the 1-qubit quantum algorithm for symmetric Boolean functions of Maslov et al. [1]. We also show that the technique of PQSP works for the 1-qubit program for Boolean functions of Cosentino et al. [2]. We construct an efficient PSM protocol for Boolean functions computable by O(log n)-depth circuits with an evaluator of 1-qubit writable workspace from their 1-qubit program [3]. Such efficient PSM protocols with space-bounded classical evaluators have not been known so far.
近年,量子計算機の研究開発が盛んに行われており,量子計算量クラスに関する理論的な研究も活発に行われている.量子計算機は古典計算機に比べ高速に計算できることが期待されており,すでに実装可能な量子計算機がスーパーコンピュータを上回る性能に達しているという研究結果も存在する[3].しかし現在実装可能な量子計算機は古典計算機に比べ扱えるビット数が少ないため,量子領域計算クラスに関する困難性を明らかにすることは重要な課題となっている. また量子計算機はすべての問題において古典計算機より高速に計算できるわけではない.量子ビットは古典ビットに比べ少ない量で多くの情報を保持することが可能だが,保持した情報を一つずつ取り出すといった操作は得意ではない.こういった性質から,量子計算機では行列演算など複数の情報を用いた演算を古典計算機より少ないステップで行い,その結果を出力するという問題に強く,実際に行列に関する様々な問題の量子アルゴリズムが考案されている.こういった量子計算量クラスに関する様々な研究成果が出る中で,古典計算量クラスとの関係性を明らかにすることは量子計算機を活用するうえで重要な指標となる.現在行列問題における古典計算量クラスと量子計算量クラスの違いとして,扱えることのできる行列の種類や,近似を行う際の精度といったことが予想されている. このような背景より,古典における領域複雑性と行列問題の精度の観点から,Doron らの研究[6] に注目した.Doron らは確率行列の第二固有値を判定する問題について,逆多項式の精度を要求する場合はBPL 完全であることを示した.しかし彼らの研究において,より簡単な問題である定数精度を要求する第二固有値問題がどれほど困難かについては議論されておらず,定数精度と逆多項式精度の第二固有値問題における困難性が同等かは不明である.そこで本研究では逆多項式精度の第二固有値問題を定数精度に確率的対数領域計算で帰着させることで,定数精度と逆多項式精度の第二固有値問題が確率的対数領域計算において同等の困難性を持つことを示そうと試みた.結果として確率的対数領域計算が可能な状況では,定数精度の第二固有値問題が一部の逆多項式精度の問題より困難であることを示した.
最近の量子コンピュータの研究は,ノイズの影響を受けやすい,NISQデバイスと呼ばれる量子コンピュータの活用が研究されている.NISQデバイスは量子ニューラルネットワーク(以下,QNN)による,古典-量子アルゴリズムで応用されている.このアルゴリズムは教師あり分類問題において,4つのステップで構成されている.(1)古典データを量子状態に埋め込む回路を初期状態に作用させる.(2)パラメータに依存する回路を適用する.(3)Z基底測定で測定をする.(4)古典最適化アルゴリズムを用いて,最適なパラメータを見つけ,量子回路を更新する.その後,更新したパラメータでテストデータを分類する. 先行研究では,アルゴリズムのステップ(1)と(2)を重要視し,ヒューリスティックに回路を設計して量子優位性を主張している.先行研究で提案されていることは,2量子ビット間のエンタングルメント回路を取り入れることと,古典ニューラルネットワークのように,量子回路を繰り返すことである.このことによって量子優位性が得られ,教師あり分類問題に関して,本質的で重要な要素であることを主張している. 本研究は,先行研究の主張を受けて,次の2つのことを主張する.1つ目は,ヒューリスティックに構成されたエンタングルメントや回路の繰り返しは,分類問題において本質的でないこと.2つ目は,分類問題において本質的に重要なことは,任意の軸回りにおける測定の最適化をすることである.提案方法は,測定により得る古典データを分析する前に,量子状態に対して個別に任意の軸回りにパラメータ化された単一回転ゲートを作用させ,最適な測定を行うことである. 本研究で使用したデータは,人工的な2値分類データと実データのIris Data Setである.これらのデータにおいて,先行研究では,分類できないと主張されているような単純な回路でも,測定最適化をすることで分類精度が95%を超える結果が得られた.また,測定最適化した回路は,調査した全ての回路に対して分類精度が向上することが確認でき,最大で7%の分類精度から91%の分類精度への向上が見られた.さらに,測定最適化を行うことで,実データであるIris Data Setに対しても,先行研究のQNN分類器の分類精度と同等の分類精度93%の結果が得られた.測定最適化は,単一の量子ビットにしか作用されず,そのパラメータ数も量子ビットに対して線形にしか増えない.以上の結果と利点により,QNNの分類問題において本質的に重要なことは,測定の最適化であると主張する.
盗聴通信路符号化などの情報理論的安全性に基づく暗号理論においては,盗聴者が用いる通信路は,正規受信者が用いる通信路よりノイズが多いことが仮定される.しかし,盗聴者の通信路を正確に特定できない場合,想定される通信路の中で一番ノイズが少ない通信路を盗聴者が用いるものとして安全性を確保する必要がある.そのため,通信路を比較するための順序を導入する必要があり,これまでもless noisy order (Korner-Marton, 1975) など,通信路に関する様々な順序が研究されてきた.中でも,二つの通信路W, V が与えられたとき,一方の通信路V が他方の通信路Wにさらにノイズを付加した通信路となる関係W > V (degraded order) は統計的にも重要である(Blackwell-Sherman-Stein, 1951). 本論文では,通信路のノイズに関する順序(degraded order) について二つ観点で数値的な研究を行った.一つは通信路の順序と情報量(相互情報量および相対レニーエントロピー)の関係についての研究であり,もう一つは,順序を判定する効率的なアルゴリズムの開発である. 最初に,通信路の順序と相互情報量および相対レニーエントロピーの関係について数値実験による研究を行った.通信路W と通信路の入力アルファベット上の確率分布P が与えられると,相互情報量I(P;W) が計算できる.相互情報量の単調性(データ処理不等式)より,二つの通信路W, V が順序関係W > V を満たす(V はW よりノイズが多い)ならば,すべての入力分布Pについて,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つ.本研究では,この命題の逆が成立するかどうかを調べるため,数値実験により,3 入力3 出力の通信路を多数調べることで反例を探した.その結果,反例として,非常に多くの入力分布P について,相互情報量の大小関係I(P;W) >_ I(P; V ) が成り立つが,順序関係W > V を満たさない例を多数見つけた.相対レニーエントロピーについても同様の単調性が成り立つことが知られている.この場合も同様に,単調性の逆の命題が成立しない多数の反例を見つけた. 次に,二つの通信路W, V が任意に与えられたとき,順序関係W > V が満たされるかどうかを判定する一般的なアルゴリズムの開発を行った.本論文では,通信路W に付加的なノイズU が加わる状況を考え,U を変えて行くことでW とU の合成通信路が通信路V に一致するかどうかを最急降下法により調べた.その際,コスト関数として確率遷移行列の成分の二乗和を用いた.また,付加するノイズU も確率遷移行列である必要がるため,U の行列成分は非負かつ行和は1 でなければならない.本論文では,U を指数分布族により表現することで,確率遷移行列の制約条件を満たしながらコスト関数を最小化するアルゴリズムを開発した.
現在最もよく使われているRSA暗号や楕円曲線暗号は,計算量的安全性に基づく公開鍵暗号系に分類される汎用量子コンピュータが実現した場合,Shor のアルゴリズム(1994)により素因数分解問題や離散対数問題が多項式時間で解かれてしまうため,RSA 暗号等の安全性が崩れることが理論的に知られている.近年,汎用量子コンピュータの開発研究において,量子デバイスのブレイクスルーが起こっている.今後20年程度の間に汎用量子コンピュータが実現される見込みが高い.Wyner の盗聴通信路符号化によれば,正規受信者と盗聴者が用いる通信路のノイズ差が利用出来る状況においては,盗聴者に対する完全秘匿を確保しながら正規受信者に誤りなくメッセージや秘密鍵を伝送する符号化が可能になる.理論的には,符号長を大きくして安全な符号を生成出来ることが分かっている.ただし,生成された符号が「実際に安全かどうか」を確認するための手段が理論的に与えられていない. 本研究では,情報理論的安全性に基づく暗号系の一つである盗聴通信路符号化をコセット符号化を用いて実現させるために,特性関数を用いて安全性評価を行うという方法を提案する. 本研究ではファネス型不等式を用いて,盗聴者の持つ情報と一様分布の1-normを経由したエントロピーによる安全性評価を行う方法を提案した.さらに,確率分布の1-normを具体的に計算することは一般に困難なので,確率分布の1-normを直接計算する代わりに,多変数特性関数の2-normで強安全性を用いた安全性評価を行う方法を提案する.その結果,計算量の大幅な削減を行うことができるということがわかり,数値実験によりその優位性を示した.