Logo
ログイン

Q&A

最終更新：2024年1月13日

QCoder について

QCoder とはなんですか？

2024年に新たにサービスを開始した量子プログラミングコンテストプラットフォームです。

従来型のプログラミングコンテストとは異なり、量子コンピュータ上で動作する 量子アルゴリズム を実装する問題が出題されます。

※ 本サービスは 2023年度未踏ターゲット事業 の支援を受けて開発・運営されています。

量子コンピュータについてよくわからないのですが、どうすればいいですか？

まずはコンテストに参加してみることをオススメします。

初めはわからない部分も多いかと思いますが、解説を参照しながら問題を解くうちに全体像が見えてくるはずです。

QCoder は量子コンピュータまったくわからない...という方から、量子コンピューティングの専門家まで、すべての人が楽しめるコンテストを目指しています。

どのようにして量子アルゴリズムを実装するのですか？

現在量子プログラミング言語（フレームワーク）として、Python 上で動作する Qiskit をサポートしています。

提出されたプログラムは量子コンピュータの実機ではなく、シミュレーターを用いて採点を行います。

※ QCoder 上のエディタでは補完や linter が動作しません。手元のコンピュータ上に Qiskit の環境構築 を行うことを推奨しています。

量子コンピューティングを勉強したいです。おすすめの教材はありますか？

以下の教材を推奨しています。

  • 初心者でもわかる量子コンピュータの計算の仕組み:
    量子コンピューティングの仕組みから Qiskit を使った量子プログラミングまで分かりやすく記述されています。
  • Basics of quantum information - IBM Quantum Learning:
    Qiskit 公式の量子コンピューティングに関するチュートリアルです（英語）。
  • Quantum Native Dojo:
    Jupyter notbook ベースの教材で量子コンピュータの基礎から応用まで幅広く学ぶことができます。
  • Qookbook:
    専用のライブラリを用いて問題を解きながら量子コンピュータの基礎や量子プログラミングを学ぶことができます。QCoder と同じく2023年度未踏ターゲット事業の取り組みです。

今後のコンテストやアップデートを知りたいです。

ぜひ X (Twitter) のフォローと Google カレンダーの登録をお願いします。

提出結果にはどのようなものがありますか？

以下の提出結果が表示されることがあります。

  • AC (Accepted): すべてのテストケースに対して正答を返したことを表します。
  • WJ (Waiting for Judging): ジャッジを待機している状態を表します。
  • WA (Wrong Answer): 少なくとも１つのテストケースに対して誤った答えを返したことを表します。
  • QLE (Qubits Limit Exceeded): 量子ビット数制限を超過したことを表します。
  • DLE (Depth Limit Exceeded): 回路の深さ 制限を超過したことを表します。
  • TLE (Time Limit Exceeded): 実行時間制限を超過したことを表します。
  • MLE (Memory Limit Exceeded): メモリ使用量制限を超過したことを表します。
  • CE (Compilation Error): コンパイル 中に何らかのエラーが生じたことを表します。
  • RE (Runtime Error): 実行中に何らかのエラーが生じたことを表します。
  • UME (Unauthorized Module Error): 利用が認められないモジュール の import が確認されたことを表します。
  • UGE (Unauthorized Gate Error): 利用が認められない量子ゲート が回路上に存在することを表します。
  • TOE (Time Out Error): 提出がジャッジされないまま一定の時間が経過したことを表します。

どのようなライブラリ・モジュールを使うことができますか？

現在、以下の Python モジュールの利用のみが認められています。

これらを除くモジュールが import されていた場合、UME (Unauthorized Module Error) が表示されます。

  • 標準ライブラリ
    • math (import math)
  • qiskit
  • qiskit.circuit.library
    • 任意のクラスを import することができます。以下は import 可能なクラスの例です。
      • HGate (from qiskit.circuit.library import HGate)
      • CXGate (from qiskit.circuit.library import CXGate)
      • MCPhaseGate (from qiskit.circuit.library import MCPhaseGate)

どのような量子ゲートを使うことができますか？

Qiskit の standard gates に分類される量子ゲートと MCPhaseGate のような複数制御ゲートの利用が認められます。

これらに該当しない以下のようなゲートの利用は禁止されており、利用時は UGE (Unauthorized Gate Error) が表示されます。

回路に量子ビットを追加することはできますか？

現在、ユーザーが量子回路の量子ビット数を変更することはできません。

量子アルゴリズムによっては、一次的なメモリとして機能する補助量子ビット（アンシラ）を必要とする場合があり、こうした状況に対応するためのアップデートを今後予定しています。

手元で量子回路を実行することはできますか？

手元の端末で自分の作成した量子回路を実行することができます。

例えば、次のコードを利用して回路の最終的な状態ベクトルを出力することができます。

開く
from qiskit import Aer, execute
 
 
def simulate(qc: QuantumCircuit):
    simulator = Aer.get_backend("statevector_simulator")
    statevector = execute(qc, simulator).result().get_statevector(qc)
    print(statevector)
 
 
if __name__ == "__main__":
    simulate(solve())

Python のコンパイルエラーとは？

Python ではコードの実行前にソースファイルからバイトコードへのコンパイルが行われます。 これは通常、実行時に自動で行われ、結果はキャッシュされますが、py_compile を用いてコンパイルを手動で行うこともできます。

QCoder では実行時間への影響を防ぐため、実行前に py_compile が行われます。

Python・ライブラリ のバージョンは？

現在、ジャッジサーバーでは Python 3.11 により提出のジャッジが行われます。

また、ジャッジに利用されるライブラリのバージョンは以下の通りです。

今後のアップデートについて教えてください。

現状、以下のアップデートが予定されています。

  • レーティングの実装
  • 英語対応

QCoder の活動に興味を持ちました。私も作問や運営に協力したいです。

アルバイトや副業として問題提供 (writer) や運営にご協力頂ける方、スポンサー企業様を募集しております。

ご興味のある方は お問い合わせ からお気軽にご連絡下さい。

量子コンピューティングについて

量子状態とはなんですか？

量子コンピュータでは、古典コンピュータのビットに相当する「量子ビット」を用いて計算を行います。

1つの量子ビットの任意の状態 ∣ψ⟩\ket{\psi} は状態 ∣0⟩\ket{0} と ∣1⟩\ket{1} の係数 a0, a1a_0,\ a_1 による重ね合わせとして次式で表すことができます。

∣ψ⟩=a0∣0⟩+a1∣1⟩\ket{\psi} = a_0\ket{0} + a_1\ket{1}

このように量子ビットは ∣0⟩\ket{0} と ∣1⟩\ket{1} の確率的な重ね合わせ状態をとることができ、「測定」により∣0⟩\ket{0} または ∣1⟩\ket{1} のどちらかに確定します。

ただし、a0, a1a_0,\ a_1 は「複素振幅」と呼ばれる複素数で ∣ψ⟩\ket{\psi} の測定時には状態 ∣0⟩\ket{0} が ∣a0∣2|a_0|^2 、状態 ∣1⟩\ket{1} が ∣a1∣2|a_1|^2 の確率で観測されます。

測定時には必ずどちらかの状態が観測されるため、複素振幅 a0, a1a_0,\ a_1 は ∣a0∣2+∣a1∣2=1|a_0|^2 + |a_1|^2 = 1 を満たします。

このような量子ビットの状態を「量子状態」と呼びます。

また、量子状態を構成する状態 ∣0⟩\ket{0} と ∣1⟩\ket{1} が

∣0⟩=(10), ∣1⟩=(01)\ket{0} = \begin{pmatrix} 1 \\ 0 \end{pmatrix},\ \ket{1} = \begin{pmatrix} 0 \\ 1 \end{pmatrix}

のようなベクトルで表されるとすると、量子状態 ∣ψ⟩\ket{\psi} は

∣ψ⟩=a0∣0⟩+a1∣1⟩=(a0a1)\ket{\psi} = a_0\ket{0} + a_1\ket{1} = \begin{pmatrix} a_0 \\ a_1 \end{pmatrix}

のようにベクトルで表すこともできます。このような表記を量子状態の「状態ベクトル」と呼びます。

次に、複数の量子ビットの量子状態を考えます。

nn 量子ビットの任意の量子状態 ∣ψ⟩\ket{\psi} は 2n2^{n} 個の状態の重ね合わせとして、次式で表されます。

∣ψ⟩=a0∣0...0⏟n⟩+a1∣10...0⏟n⟩+...+a2n−1∣1...1⏟n⟩=(a0⋮a2n−1)\ket{\psi} = a_0\ket{\underbrace{0...0}_n} + a_1\ket{\underbrace{10...0}_n} + ... + a_{2^n-1}\ket{\underbrace{1...1}_n} = \begin{pmatrix} a_0 \\ \vdots \\ a_{2^n - 1} \end{pmatrix}

ただし、11 量子ビットの場合と同様に、∣a0∣2+∣a1∣2+...+∣a2n−1∣2=1|a_0|^2 + |a_1|^2 + ... + |a_{2^n-1}|^2 = 1 が成り立ちます。

例えば 22 量子ビットの量子状態には ∣00⟩, 12(∣00⟩+∣11⟩), 14(∣00⟩+∣10⟩+∣01⟩+∣11⟩)\ket{00},\ \frac{1}{\sqrt{2}} (\ket{00} + \ket{11}),\ \frac{1}{\sqrt{4}}(\ket{00} + \ket{10} + \ket{01} + \ket{11}) などが考えられます。

計算基底状態とは？

計算基底状態は ∣0⟩\ket{0} や ∣10⟩, ∣111⟩\ket{10},\ \ket{111} のような量子状態を構成するそれぞれの状態を指します。

例えば 22 量子ビットの量子状態

∣ψ⟩=14(∣00⟩+∣10⟩+∣01⟩+∣11⟩)\ket{\psi} = \frac{1}{\sqrt{4}}(\ket{00} + \ket{10} + \ket{01} + \ket{11})

は 22 量子ビットの計算基底状態 ∣00⟩, ∣10⟩, ∣01⟩, ∣11⟩\ket{00},\ \ket{10},\ \ket{01},\ \ket{11} の一様な重ね合わせ状態です。

計算基底状態を2進数ではなく10進数を用いて ∣0⟩⏟10進数=∣00⟩⏟2進数, ∣1⟩=∣10⟩, ∣2⟩=∣01⟩, ∣3⟩=∣11⟩\underbrace{\ket{0}}_{\text{10進数}} = \underbrace{\ket{00}}_{\text{2進数}},\ \ket{1} = \ket{10},\ \ket{2} = \ket{01},\ \ket{3} = \ket{11} のように表記することもあります。

量子ゲートとはなんですか？

量子コンピュータでは「量子ゲート」という概念を用いて、量子状態を操作します。

例えば、XX ゲートと呼ばれる量子ゲートは量子ビットの計算基底状態を反転します。

∣0⟩→X∣1⟩∣1⟩→X∣0⟩12(∣0⟩+∣1⟩)→X12(∣0⟩+∣1⟩)\begin{align} \ket{0} &\xrightarrow{X} \ket{1} \nonumber\\ \ket{1} &\xrightarrow{X} \ket{0} \nonumber\\ \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) &\xrightarrow{X} \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) \nonumber\\ \end{align}

XX ゲート以外にも多様な量子ゲートが存在します。

それぞれの量子ゲートの意味や役割を理解しておくと、今後の問題を解く際に役立つかもしれません。

オラクルとはなんですか？

オラクル OO とは、量子アルゴリズムの中で使われる何らかの操作をブラックボックスとして扱う際に使われる用語です。

オラクルをブラックボックスとして実装は考えずに、インターフェース（入力と出力）を定めることで、それを扱う上流の量子アルゴリズムの複雑さをオラクルの呼び出し回数で評価できます。

ただし、当然オラクル自体も量子回路として実装される必要があります。

入力と出力を 計算基底状態 とする何らかの関数 ff を定めて、以下のようにオラクル OO を定義することがあります。

  • 入力と出力先が同じ状態の場合：O∣x⟩=∣f(x)⟩O\ket{x} = \ket{f(x)}
  • 入力と出力先が異なる状態の場合：O(∣x⟩⊗∣y⟩)=∣x⟩⊗∣y⊕f(x)⟩O(\ket{x} \otimes \ket{y}) = \ket{x} \otimes \ket{y \oplus f(x)}

オラクルを作用させたとき、関数 ff は対象の量子状態に含まれるすべての計算基底状態に作用することに注意してください。

以下の Web ページも参考にしてください。

回路の深さとはなんですか？

量子回路では、複数の量子ゲートをテトリスの要領で、各量子ビットに積み重ねるように配置し、「どの量子ゲートがどのような順番でどの量子ビットに作用するか」を記述します。

回路の深さとは、積み重なるように配置された量子ゲートの層の数（深さ）を表します。

回路の深さ Quantum Circuits - IBM Quantum Documentation より

量子回路を実行することは、この層を順番に量子ビットに作用させていくことと考えられるため、古典アルゴリズムの時間計算量に似た指標と解釈することもできます。

QCoder では、Qiskit の QuantumCircuit クラスの depth 関数の返り値を回路の深さとして扱います。

グローバル位相とはなんですか？

ある量子状態 ∣ψ⟩\ket{\psi} に対して、eiθ=cos⁡(θ)+isin⁡(θ)e^{i\theta} = \cos(\theta) + i\sin(\theta) をかけたような量子状態 ∣ψ(θ)⟩=eiθ∣ψ⟩\ket{\psi(\theta)} = e^{i\theta}\ket{\psi} を考えます。ただし、ii は虚数、θ\theta は何らかの実数を表します。

このとき、∣ψ⟩\ket{\psi} と ∣ψ(θ)⟩=eiθ∣ψ⟩\ket{\psi(\theta)} = e^{i\theta}\ket{\psi} を「グローバル位相 θ\theta を除いて等しい量子状態」といいます。

例えば、∣0⟩\ket{0} と −∣0⟩-\ket{0} はグローバル位相 θ=π\theta = \pi を除いて等しいといえます。

グローバル位相は量子状態の測定結果に影響を及ぼさないため、グローバル位相の異なる量子状態を等価なものとしてジャッジを行います。