森研究室 東京工業大学 情報理工学院 数理・計算科学系

本研究室の研究紹介をします。

主な最近の研究

ランダム量子回路サンプリング問題の古典的困難性 FOCS 2021

ランダムな量子回路の出力分布を古典計算機でシミュレートすることの困難性を示すことは量子計算の分野では大きな未解決問題である。 本研究ではゲート数 \(m\) のランダムな量子回路の出力確率を加法的誤差 \(\exp\{-\Omega(m\log m)\}\) で計算する問題が \(\mathsf{BPP}^{\mathsf{NP}}\) 帰着のもとで \(\#\mathsf{P}\)-hard であることを示した。 その帰結として、多項式階層が崩壊しないという仮定のもとで、上記の問題は古典計算機では効率的には解けないことを示した。

グラフ彩色量子アルゴリズム LATIN 2020 Algorithmica 2022

グラフ彩色問題は最もよく知られているNP完全問題のひとつである。現在知られている最も高速な古典アルゴリズムは\(O^*(2^n)\)時間でグラフ彩色問題を解くことができる。 グラフ彩色問題に対し、古典アルゴリズムよりも効率的な量子アルゴリズムが存在するかどうかは知られていなかった。 本研究では\(O(1.914^n)\)時間でグラフ彩色問題を解く量子アルゴリズムを示した。

非適応型測定ベース量子計算 Quantum Information & Computation 2019

量子計算の最も標準的なモデルは量子回路モデルであるが、測定ベース量子計算のモデルも同等の計算能力を持つことが知られている。 より具体的には、線形関数を計算する計算機を使って、あらかじめ用意されたクラスタ状態を適応的に測定することで、任意の多項式サイズの量子回路をシミュレートすることができる。 本研究では測定を非適応的なものに限定した場合に効率的に計算できる論理関数をその\(\mathbb{F}_2\)多項式表現を用いて特徴付けた。 またこの計算モデルを「二段」にすると、多数決関数等の「一段」では効率的に計算できない論理関数が効率的に計算できることを示した。

XORゲームの最大勝率による通信複雑度の下界の導出 Quantum Information & Computation 2017

通信複雑度は理論計算機科学における重要な複雑性尺度である。 その汎用的な下界として Linial と Shraibman による \(\gamma_2\) 下界(STOC 2007)が存在する。 その導出は難しくはないものの完全に数学的なものであり、その操作的な意味は明らかではない。 本研究では、量子力学の基礎付けの研究で Pawlowski らによって考案された「情報因果律」(Nature 2009)の研究の中で得られたプロトコルを改良することで、 \(\gamma_2\) 下界を特別な場合として含む下界のクラスを操作的な意味のある方法で導出した。

情報の観点からの量子力学の基礎付け Physical Review A 2016

量子力学の持つ最大のCHSH確率が \((2+\sqrt{2})/4\approx 0.854\) である一方で、no-signaling 条件を満たす理論で CHSH確率 \(1\) を持つものが存在する。 この事実より「量子力学の許すCHSH確率を操作的に意味のある条件で特徴付けられないだろうか？」という問題意識が生まれる。 Brassard らは、CHSH確率が \((3+\sqrt{6})/6\approx 0.908\) より大きい理論のもとでは任意の関数の通信複雑度が1ビットになることを示した(PRL 2006)。 つまり、「自然は「任意の関数の通信複雑度が1ビットになる」ということを許さない」ということを自然への要請とすれば、 CHSH確率が \(0.908\) 以下でなくてはならないことになる。 しかし、量子力学の持つ最大のCHSH確率 \(0.854\) とはギャップが存在する。 本研究では、理論計算機科学の数理的道具である「二元関数のフーリエ解析」の手法を用いることで、Brassard らの「バイアス増幅」の手法を一般化したとしても、この \(0.908\) という閾値を改善できないことを示した。

学生の研究テーマ