量子超越、という言葉は結構あいまいです。今のところ量子超越が達成されたという論文はGoogleと中国のチームから二報でていますが、現実的な問題が解けたというわけではありません。
量子アルゴリズムは、古典の対応物に対して指数関数的に高速化する場合があります。そんな意味で、計算の複雑さの理論から、量子アルゴリズムが高速だから、古典では到底解けない問題を量子コンピュータで解けたら量子超越か？と思うかもしれません。
しかしそうすると問題が出てきます。古典コンピュータで難しいとされる巡回セールスマン問題は、量子コンピュータで高速に解けるかというと、わかっていません。巡回セールスマン問題はO(N^k)のように解く多項式アルゴリズムがあるか、O(exp(N))のように解くしかないのか、それさえもわかっていません。
もし、巡回セールスマン問題をO(exp(N))で解くアルゴリズムがあれば、グローバーの探索アルゴリズムを使うことで、O(sqrt(exp(N))くらいにはなります。ですがそれでも実用にはなりません。
量子化学の問題をもう少し正しく、基底状態のエネルギーを求めることとします。古典コンピュータででは、波動関数も求めますが、波動関数は物理的実体ではありませんし、データを読み出すだけでもたいへんなので、量子コンピュータでは求めるの意味を定義するには若干の議論があると思います。だとしても、残念ながら、基底状態のエネルギーを求めるのは、QMA-完全といわれる問題になります。励起状態も同じです。これは古典コンピュータでいうところの巡回セールスマン問題(NP-完全)と、似たような問題とされています。
従って、どんなに頑張っても量子コンピュータを使って多項式程度の時間で基底状態を正確に求めるのは難しいと考えられています。しかし、QMA-完全の問題はすべてが難しいわけでもなく、一部の問題は簡単に解けます。ある巡回セールスマン問題は簡単に解ける場合があるのと同じです。そのような問題で、古典では難しいが、量子コンピュータでは簡単に解けるQMA-完全な問題を探す必要があるわけです。
このような試みとしては、qubitは波動関数を多項式程度のリソースでエンコードできる、からスタートするのが良いでしょう。古典では波動関数はどうやっても指数関数的なメモリを必要とします。以下に例を示します。
Helgakerの教科書p.525からとってきました。波動関数をスレーター行列式で書いた場合 - これは一般的なものだと思います - 何個必要か？です。これだとすこし曖昧なので、2k電子を2k軌道に入れた場合を考えてみます。すると、20電子を20軌道に入れた場合、波動関数は341億次元のベクトルとなります。これはかなり大きいです。binary64(倍精度)実数で考えた場合、31GiB程度となります。今のコンピュータでは何とかできそうです。
ただし! 表を見るとkが大きくなると必要なスレーター行列式は、一桁ずつ大きくなっていきます。指数関数的に大きくなってゆきます。これは波動関数を保持するだけでも、少し系が大きくなると大変厳しくなってゆくということを示します。例えば2k=40の場合はbinary64で波動関数を持つと10^22 bytes = 18000000000 TiBくらい必要になって、明らかに(今の)古典コンピュータでは対応できない大きさになってきます。ただ技術の進歩はわかりませんから、もしかしたらそんなメモリもできるかもしれません。でも近い将来ではほぼ100%無理だと思われます。
量子コンピュータでは、このような系は80qubitあれば波動関数だけは表現できます。まぁ余裕を見て100qubitあれば、としましょう。これは可能性を感じます。化学の問題は厳密解のエネルギーを100とすると、平均場近似で99を得ることができるといわれています。これは多くの問題で実際にそうです。従ってQMA完全といいながらも、化学の問題の大部分は(巡回セールスマン問題でいったように)簡単に解ける可能性があることを示唆します。だから皆さんは化学の問題に挑戦しているのでしょう。
さて量子超越はどこでしょうか。曖昧な言い方になりますが、個人的には、やはり量子化学の問題で比較的大きな - 40軌道40電子、100qubitくらいの問題が解けたら、となると思います。現実は理論とは違います。ショアのアルゴリズムを量子コンピュータに乗せるのは大変です。おそらく近い将来はできないと思います。だから、個人的には量子超越は量子化学の問題で、今の古典コンピュータでは解けない問題が解けたとき、になると思います。