理論計算機科学を背景に，主に，量子アルゴリズムや量子計算量理論の基礎研究に従事してきました．以下では，これまで行った代表的な研究成果を３つのカテゴリに分けて説明します．
分散計算における量子優位性
ネットワークで接続された多数の計算機が協調して行う計算分野（分散計算）において，量子計算機・量子通信を用いた場合（量子分散計算），既存（非量子）の分散計算（古典分散計算）と比較して，どのような優位性があるかについて理論研究を行なってきました．
分散計算において，「リーダー選挙問題」（＝リーダーを計算機同士で自律的決定する問題）は，同分野の教科書で必ず扱われる重要かつ基本的な問題です．論文[1,2]では，量子通信路で接続された量子計算機を使用することにより、有限時間内に確率１で，この問題を解くアルゴリズムを考案しました（計算機数nに対してO(n^2)のメッセージ回数）．この問題は、古典通信路と古典計算機を用いた場合、各計算機にあらかじめ優先度（例：ユニークなID）を与えるなどの前提なしには有限時間内に確率１では解けないことが数学的に証明されており，本成果は、どんなに古典通信・古典計算を行っても古典分散計算では達成不可能な、応用上重要な問題に対して、高速量子アルゴリズムを与えた点で世界的に高い評価を受けています。高速量子アルゴリズムと言えば，例えば，素因数分解を行うショアの量子アルゴリズムや，探索を行うグローバの量子アルゴリズムが有名であるが，これらは古典計算でも時間をかければ解ける問題を指数倍もしくは多項式倍高速に解けることを主張している点で「計算量的な量子優位性」を示しています．これに対し，本成果は「計算可能性における量子優位性」を示しています.
本成果は，単に「リーダー選挙問題」という特定の問題に対して，量子優位性を示したことにとどまりません．例えば，古典分散計算において，各計算機がユニークなIDを持たない状況下では解けないが，ユニークなIDを持つ状況ならば簡単に解ける重要な問題が数多く知られています．リーダーが一度決定されればユニークなIDを各計算機に付与することができることから，本成果は，量子計算・量子通信を使えるならば，ユニークなIDを持つかどうかの前提条件によらず，上記の問題が全て解けるという意味で，広いクラスの問題に対して「計算可能性の量子優位性」を示しています．
また，論文[3]で得られた古典分散計算のテクニックを補助的に使うことにより，量子通信を最初のわずか１ラウンドに限定しても，リーダー選挙問題を解くことができ量子優位性を示すことができます(論文[1]記載の2nd Algorithm)．なお，論文[3]は，各計算機にあらかじめ優先度を与えるなどの前提がない状況下で計算可能な任意の問題に対し，計算機数に対して多項式通信量・線形メッセージ回数で解く古典アルゴリズムを世界で初めて与えたものです．
[1] Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto. Exact Quantum Algorithms for the Leader Election Problem. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS ’05), Springer, Lecture Notes in Computer Science, 3404, pp. 581–592, 2005. (full paper: arxiv:0712.4213 )
[2] Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto. Exact Quantum Algorithms for the Leader Election Problem. ACM Transactions on Computation Theory, 4(1), pp. 1-24, 2012. [DOI]
[3] Seiichiro Tani. Compression of View on Anonymous Networks — Folded View –. IEEE Transactions on Parallel and Distributed Systems, 23(2), pp. 255–262, 2012. [DOI]
[4] Hirotada Kobayashi, Keiji Matsumoto and Seiichiro Tani. Simpler Exact Leader Election via Quantum Reduction. Chicago Journal of Theoretical Computer Science, 2014(10), pp. 1-31, 2014.
[5] Seiichiro Tani. A Fast Exact Quantum Algorithm for Solitude Verification. Quantum Information & Computation, 17(1-2), pp. 15-40, 2017. [DOI]
計算機単体での計算における量子優位性
計算機単体での計算において，量子計算機が古典計算に対して，どのような問題に対して，どの程度優位性があるかについて理論研究を行なってきました．ここでは特にクロー発見問題の研究について説明します．
クロー発見問題は，同じ値域を持つ複数の関数が与えられたとき，同じ値に写像される要素の組を発見するというシンプルな問題です．例えば，二つの関数f:X→Z,,g:Y→Zが与えられたとき，f(x)=g(y)を満たす(x,y)が存在すれば(x,y)を出力し，存在しなければ，その旨を出力するのが問題の目的です．論文[1]では，k個の関数がブラックボックスとして与えられたとき，クロー発見問題を解く高速な量子アルゴリズムを与えました．本アルゴリズムは，全てのkに対して，関数の評価回数において古典計算より漸近的に優れていることを理論的に保証しています．特に，最も重要なk=2の場合は，関数の評価回数において，従来から知られていた（量子計算の）下界と一致しており，最適です．
クロー発見問題を考える動機は，その数学興味に加えて，暗号との深い関連にある．多くの暗号で，クロー発見問題が高速には解けないことを安全性の根拠にしており，そのような暗号の安全性解析にはクロー発見問題を解くために要する計算量評価が欠かせません．特に近年，量子計算機の開発が世界中で進められるようになり，量子計算機を用いた強い攻撃にも耐える暗号（＝耐量子計算機暗号）が注目されています．このような暗号の安全性解析には，量子計算機を使った攻撃手法（＝量子アルゴリズム）の研究が本質的です．本成果は，クロー発見問題を安全性の根拠にしている暗号の強度解析に応用されています．例えば，現在進行中の米国NISTによる耐量子計算機暗号の標準化において，最終ステージまで残った主要方式の一つである超特異楕円曲線暗号の強度評価に応用されました．なお，暗号の強度解析では，攻撃アルゴリズムを量子回路として実装したときに必要な計算資源（ゲート数・量子ビット数）を見積もる必要があります．特に，基本演算である算術演算中でも加算回路は重要であり，我々の効率的な加算量子回路[2]が応用されています．
また，暗号分野では，しばしば与えられる関数がランダム関数であることを仮定します．この仮定のもとでは，クロー発見問題はさらに高速に解くことができます．具体的には，k個の関数がブラックボックスとして与えられたときに，関数の評価回数・時間計算量において，下界と一致する最適な量子アルゴリズムを与えました[3]．
[1] Seiichiro Tani. Claw finding algorithms using quantum walk. Theoretical Computer Science, 410(50), pp. 5285-5297, 2009. [DOI]
[2] Yasuhiro Takahashi, Seiichiro Tani and Noboru Kunihiro. Quantum Addition Circuits and Unbounded Fan-Out. Quantum Information and Computation, 10(9-10), pp. 872-890, 2010. [DOI]
[3] Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani and Keita Xagawa. Quantum algorithm for the multicollision problem. Theoretical Computer Science, 842, pp. 100-117, 2020. [DOI]
計算複雑さ
本節では，量子回路および二分決定グラフに関する計算複雑さの成果について説明します．
（１）論理回路の計算複雑さは，P vs NP問題や多項式階層などの計算量クラスと深い関係があり，計算量理論の中心的テーマです．量子回路の計算複雑さも，量子計算量理論の主要テーマの一つであり，様々な量子回路クラスの計算能力が研究されています．その中でも，回路の深さが浅い（ビット数の対数の多項式で抑えられる深さを持つ回路）クラスは，実用面での重要性や，領域限定計算量クラスとの関係から，重要な研究ターゲットになっています．特に，ほとんどの重要な算術演算（例えば，加算や乗算）は，対数深さの多項式サイズ論理回路で実現できる一方で，それ以下の深さ（例えば，入力ビット数によらない定数の深さ）の多項式サイズ論理回路では実現できないことが知られています．これに対して，量子回路においては，論理回路でも仮定されているある種の基本ゲート（ファンアウトゲート）を仮定すると，多くの重要な算術演算が，定数の深さの多項式サイズ量子回路で実現できることを示しました[1]．これは，業界で10年以上未解決だった計算量クラスに関する問題を，（おそらく大方の予想とは異なる方向で）解決したものです．実用的には，ファンアウトゲートを物理的に実現しようとする研究もあり，古典回路では実現不可能な高速算術回路を実現できる可能性があります．また，古典回路を補助的に使うことによりファンアウトゲートを定数深さの量子回路で実現できることが知られているため，本成果を用いることで，ノイズ耐性のある算術演算量子回路を構成することができます．
[1] Yasuhiro Takahashi and Seiichiro Tani. Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. Computational Complexity, 25(4), pp. 849–881, 2016.
(doi: 10.1007/s00037-016-0140-0)
（２）二分決定グラフ（OBDDs: Ordered binary decision diagrams)とは，論理関数の非巡回有効グラフによる表現であり，ある条件を満たす既約表現に限定すれば，論理関数の等価性判定がOBDDサイズに対して線形時間で可能であるという有用な性質があります．OBDDのサイズは，論理変数の数に対して，指数サイズになりえますが，実用の場面で出現する関数に対してしばしば非常に小さなサイズ（例えば線形サイズ）で表現できることから，計算機上で論理関数処理を行う際に用いるデータ構造として最もよく使用されるものの一つになっています．また，計算量理論の分野において，領域計算量の解析で使われるBranching Program (BP) の特殊ケースがOBDDであることから，その計算量理論的側面からも興味が持たれてきました．実用と理論の双方の観点において，OBDDに関する最も重要な問題は，その最小化問題です．OBDDは，任意の論理関数に対して，論理変数を逐次的に評価するプロセスをグラフで表現したものと考えることができますが，論理変数を評価する順序（変数順序）の選び方により，同じ関数を表すOBDDであっても，そのサイズが指数的に異なる例が知られています．このため，OBDDを最小にする変数順序を見つける問題は，実用面で極めて重要です．この問題がNP完全であることを初めて証明し，P≠NPのもとでは多項式時間で解けないことを示しました[1]．NP完全の証明は多くの問題に対して示されていますが，OBDD最小化問題は，理論研究者ばかりでなく応用研究者にとっても，特に注目されていた問題であったため，OBDDの標準的な教科書(C. Meinel & T. Theobald著, Springer [リンク])で詳しく説明されるなど世界的な評価を得ました．この後，さらに特殊な場合でもNP困難であることや近似不可能性の結果が発表されるなど，後続の研究の源流となりました．この他，グラフに関連する組合せ問題をOBDD で解く場合に，問題の構造とOBDD のサイズの関係を理論的に明らかにするなどOBDDに関する一連の研究を行いました[2-4]. さらに，これらの成果で得た知見をベースに，OBDDを最小化する変数順序を発見する高速量子アルゴリズムを与えました[5]．
[1] Seiichiro Tani, Kiyoharu Hamaguchi and Shuzo Yajima. The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram. IEICE Transactions on Information and Systems, E79-D(4), pp. 271-281, 1996.[link] (A preliminary version in Proc. 4th International Symposium on Algorithms and Computation (ISAAC 1993), pp.389–398, 1993. [DOI])
[2] Seiichiro Tani and Hiroshi Imai. A Reordering Operation for an Ordered Binary Decision Diagram and an Extended Framework for Combinatorics of Graphs. In Proceedings of the Fifth International Symposium on Algorithms and Computation (ISAAC’94), Springer-Verlag, Lecture Notes in Computer Science, pp. 575–583, 1994.
[3] Seiichiro Tani, Kiyoharu Hamaguchi and Shuzo Yajima. The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram. IEICE Transactions on Information and Systems, E79-D(4), pp. 271-281, 1996.[link] (A preliminary version in Proc. 4th International Symposium on Algorithms and Computation (ISAAC 1993), pp.389–398, 1993. [DOI])
[4] Kyoko Sekine, Hiroshi Imai and Seiichiro Tani. Computing the Tutte polynomial of a graph of moderate size. In Proceedings of the 6th International Symposium on Algorithms and Computation (ISAAC 1995), Springer Berlin Heidelberg, Lecture Notes in Computer Science, 1004, pp. 224-233, 1995.
[5] Seiichiro Tani. Quantum algorithm for finding the optimal variable ordering for binary decision diagrams, Theoretical Computer Science, 1041(7):15230, 2025.