ブログ

715キュビットの回路を生成し、Classiqで他のSAT問題を解決する

25
7月
,
2022

このノートでは、Classiqプラットフォームを使って制約充足問題を解く方法について説明します。次に、715量子ビットの回路を生成する、より複雑な例を示します。

私たちは制約された世界に生きている

制約充足可能性(SAT)問題はどこにでもある。この難しい問題のクラスは、「形式的検証、人工知能、オペレーションズ・リサーチ、計算生物学、暗号、データマイニング、機械学習、数学など」のようなアプリケーションで、特定のケースを定義して解くことを目的とした国際会議が存在するほど広範囲に及んでいる。どの業界にも、何らかの制約が存在する。例えば、複雑な可動部を持つあらゆる産業に当てはまるロジスティクス。限られた容積に製品を梱包することは、制約充足可能性問題の一例に過ぎず、このような問題がいかに早く解けなくなるかは容易に想像できる。人間一人で、荷物の積まれた車を構成することができ、チーム一人で、物資の入ったクローゼットを手配することができる。しかし、大洋を横断する輸送コンテナの利用を最適化する最善の方法は何だろうか?量子コンピューティングは、これらの充足可能性問題を定義し、グローバーの探索アルゴリズムを使って実装した場合、古典的なコンピューティングに比べて2次的なスピードアップを提供する。

カックロのパズル

SAT問題の面白い例として、Classiq Coding Competitionの問題のひとつである「カックロ」がある。カックロは数独やクロスワードパズルに似た論理パズルである。目標は、各行と各列の内容が指定された合計になるように、そして行や列の2つのセルの番号が同じにならないように、空白のセルを数字で埋めることである。競技会では、回路を単一量子ビットユニタリゲートとCXゲートに分解した後、オラクルで最も少ないCXゲートでグローバー探索を使って以下のパズルを解くという問題が出された。

このパズルを手作業で解き始めると、ゲームのルールはオラクルが解くためのブーリアンロジックで書けることがわかる。X5とX6は足して1、X4とX6は足して1、といった具合だ。ルール間の重複に気づいた後、私たちはそれらを符号化する単純化された制約のリストを定義しました。これらの制約がどのように削減されたかについては、こちらを参照してください。以下が満たすべき制約です。


"(x0 != x1)と" 
"(x2 + 2 != x3)と" 
"(x3 != x4) と" 
"(x1 != x3)と"
"(x3 != x5)と"  
"(x5 != x6)と" 
"(x0 != x2)と"
"(x1 != x5)と" 
"(x4 != x6)と" 
"(x3 == 2)と" 
"(x2 + x4 + x3 == 3)"

ClassiqでKakuroを解く方法

このノートではClassiqのPython SDKを使って問題を解いていきますが、すべての結果はVisual Studio CodeのClassiqエクステンションでも実現できます。ClassiqのPython SDKを使ってこの問題を解くには、組み込みの算術関数の中で制約を式として定義するだけです。変数をシングル量子ビット・レジスタとして宣言しますが、X3はダブル量子ビット・レジスタ(0, 1, 2, 3の値を取ることができるため)として宣言します。 


from classiq import ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic.
from classiq.interface.generator.model import Constraints, Preferences.
from classiq.interface.generator.model.preferences.preferences import (
    CustomHardwareSettings、
)

EXPRESSION = "(x0 != x1) and".+ \
             "(x2 + 2 != x3) and "+ \
             "(x3 != x4)と" + \
             "(x3 != x1)と" + \
             "(x5 != x6) and "+ \
             "(x0!=x2)と" + \+ \
             "(x1 != x5)と" + \+ \
             "(x4 != x6) and "+ \
             "(x3 == 2)と"+ \
             "(((x2 + x4) + x3)%4 == 3)"


oracle_params = 算術式(
    expression=EXPRESSION、
    定義=dict(
        x0=RegisterUserInput(size=1)、
        x1=RegisterUserInput(size=1)、
        x2=RegisterUserInput(size=1)、
        x3=RegisterUserInput(size=2)、
        x4=RegisterUserInput(size=1)、
        x5=RegisterUserInput(size=1)、
        x6=RegisterUserInput(size=1)
    ),
    uncomputation_method="naive"、
)

次に、ハードウェア設定を指定し、CXゲートとUゲートの基本ゲート・セットを宣言する。最後に、CXゲート数を最適化し、回路を合成する。



custom_hardware_settings = CustomHardwareSettings(basis_gates=["cx", "u"])
preferences = Preferences(custom_hardware_settings=custom_hardware_settings)

model_designer = ModelDesigner(constraints=Constraints(optimization_parameter='cx'), preferences=preferences)
model_designer.Arithmetic(params=oracle_params)

circuit = model_designer.synthesize()

circuit.show_interactive()
print(f"{circuit.transpiled_circuit.depth=}")
print(f"{circuit.transpiled_circuit.count_ops['cx']=}")

このコードを実行すると、Classiqの合成エンジンはさまざまな最適化手法を数秒以内に検討し、目的の機能を満たす回路を返します。以下に示す対話型回路と、その結果の深さとCXゲート数を示します


circuit.transpiled_circuit.depth=197
circuit.transpiled_circuit.count_ops['cx']=190

インタラクティブ・ビジュアライゼーション

クラシックのロゴ

スクリプトにエラーがありました

1ヵ月間にわたるコンペティションで選手たちが作成した他のソリューションは、こちらをクリックしてご覧ください。

パズルを超えて

Classiqプラットフォームを使えば、より高度なSAT問題も解くことができます。量子コンピュータが実世界の価値を生み出すには、数百から数千の量子ビットが必要になると予測されており、Classiqは将来の大規模回路にも対応しています。次のコードブロックは10変数、100節のオラクルから 715量子ビットの回路を合成しています。


from classiq import ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic

EXPRESSION = "(((x0 または ~x1 または ~x8) and (~x7 または ~x5 または ~x6)) and ((~x4 または ~x3 または ~x0) and (x0 または x3 または x7)) and ((~x5 または x0 または ~x2) and (x0 または ~x7 または ~x9))".~x2)と((x0 または ~x7 または ~x9))と((~x5 または x4 または x6)と((x4 または ~x8 または x9))と((x6 または ~x5 または ~x7)と((x8 または ~x6 または ~x4)))と"+ \
             "(((x5または~x3または~x7)および(x7または~x1または~x4))および((~x5または~x6または~x2)および(~x8または~x0または~x4))および((x4または~x8または~x5))と((~x0 or x6 or ~x7))と((x4 or x2 or ~x8)と((~x6 or ~x9 or x0))と((x9 or ~x0 or x7)と((~x7 or x5 or ~x9)))と"+ \
             "(((x6または~x0または~x9)および(x5または~x8または~x1))および((x3または~x6または~x2)および(x7または~x5または~x8))および((x8または~x6または~x3)および(x3または~x1または~x4))と((~x3または~x9または~x4)と((~x8または~x1または~x4))と((~x6または~x3または~x9)と((~x4または~x6または~x3)))とがある。+ \
             "(((~x0 or x8 or x5) and (~x6 or x7 or ~x4)) and ((x9 or ~x8 or ~x4) and (~x4 or x2 or ~x0)) and ((x7 or x6 or ~x5))と((x7又は~x2又は~x8))と((x5又は~x6又は~x7)と((~x2又は~x3又は~x0))と((x2又は~x3又は~x5)と((~x3又は~x8又は~x5))と"+ \
             "(((x6 または ~x1 または ~x9) および (~x0 または ~x1 または x4)) および ((x3 または x7 または ~x2) および (x4 または x2 または ~x0)) および ((~x0 または ~x5 または x4) および(~x3または~x7または~x1))と((~x0または~x3または~x7)と((~x9または~x5または~x8))と((~x6または~x7または~x0)と((~x6または~x1または~x8)))とがある。+ \
             「(((x8または~x4またはx1)および(x4またはx2または~x3))および((~x0または~x2または~x5)および(~x0または~x8または~x4))および((~x6または~x9または~x0)))と((x4 or x0 or x9))と((x8 or ~x7 or x9)と((x0 or ~x1 or ~x2))と((~x7 or x2 or x5)と((x6 or x8 or x3)))と"+ \
             "(((~x4またはx6またはx8)および(x9または~x6または~x4))および((~x9または~x6またはx2)および(~x2またはx7またはx6))および((x3または~x9またはx1)および(x8または~x7または~x9))と((x2または~x1またはx0)と((x2または~x6または~x4))と((~x3または~x6または~x8)と((~x0または~x4またはx2)))とがある。+ \
             "(((x2または~x0またはx8)および(~x8または~x5または~x9))および((x5または~x8または~x9)および(x1または~x3または~x0))および((~x6または~x9または~x7))と((~x9 or x1 or x2))と((x0 or ~x1 or ~x8)と((x8 or ~x6 or x3))と((~x8 or x1 or ~x2)と((x4 or ~x1 or x0)))と"+ \
             "(((x9 または x3 または ~x0) および (x5 または ~x9 または x2)) および ((~x0 または x5 または ~x9) および (x1 または x8 または ~x5)) および ((~x7 または ~x0 または x4) および(~x1または~x7または~x5))と((x8または~x0または~x6)と(~x7または~x5または~x9))と((x5または~x6または~x8)と(~x6または~x9または~x3)))と"+ \
             "(((~x9 or ~x1 or x3) and (x2 or ~x5 or ~x6)) and ((~x2 or x1 or ~x4) and (x0 or x8 or ~x9)) and ((~x4 or x1 or x7))および((x8または~x4または~x0))および((x1または~x0または~x4)および((~x9または~x8または~x1))および((~x5または~x1または~x8)および((~x4または~x3または~x8)))")



oracle_params = 算術式(
    expression=EXPRESSION、
    定義=dict(
        x0=RegisterUserInput(size=1)、
        x1=RegisterUserInput(size=1)、
        x2=RegisterUserInput(size=1)、
        x3=RegisterUserInput(size=1)、
        x4=RegisterUserInput(size=1)、
        x5=RegisterUserInput(size=1)、
        x6=RegisterUserInput(size=1)、
        x7=RegisterUserInput(size=1)、
        x8=RegisterUserInput(size=1)、
        x9=RegisterUserInput(size=1)、
    ),
    uncomputation_method="naive"、
)

model_designer = ModelDesigner()
model_designer.Arithmetic(params=oracle_params)

circuit = model_designer.synthesize()

circuit.show_interactive()

このコードで生成された 715量子ビットのインタラクティブ回路はこちらで見ることができる。

また、生成された回路を量子クラウド・サービス上に展開することも難しくない。例えば、Classiqプラットフォームで解いたSAT問題をAmazon Braket上で実行した詳細な例をご覧ください。 

最終的には、量子コンピューターはロジックパズルや単純な演算のためだけに使われることはないだろう。量子コンピューターが提供する利点は、検索(グローバーのアルゴリズムでSAT問題を解く)、パターン認識(量子機械学習)、最適化(古典と量子のハイブリッドQAOA)など、大規模なデータセットを扱うあらゆる産業で、これまでよりもはるかに高速に活用されるようになるだろう。量子を探求するコストは低く、それを無視すると壊滅的な打撃を受ける可能性があるため、量子コンピューティングはテクノロジーの未来にとって最大の保険のひとつとなる。Classiqのプラットフォームは、量子のユースケースに興味がある方にも、量子コードをより高いレベルに引き上げたい方にも、専門的な知識を提供します。 

Classiqと革新的なソフトウェアの詳細については、こちらからお問い合わせください。

このノートでは、Classiqプラットフォームを使って制約充足問題を解く方法について説明します。次に、715量子ビットの回路を生成する、より複雑な例を示します。

私たちは制約された世界に生きている

制約充足可能性(SAT)問題はどこにでもある。この難しい問題のクラスは、「形式的検証、人工知能、オペレーションズ・リサーチ、計算生物学、暗号、データマイニング、機械学習、数学など」のようなアプリケーションで、特定のケースを定義して解くことを目的とした国際会議が存在するほど広範囲に及んでいる。どの業界にも、何らかの制約が存在する。例えば、複雑な可動部を持つあらゆる産業に当てはまるロジスティクス。限られた容積に製品を梱包することは、制約充足可能性問題の一例に過ぎず、このような問題がいかに早く解けなくなるかは容易に想像できる。人間一人で、荷物の積まれた車を構成することができ、チーム一人で、物資の入ったクローゼットを手配することができる。しかし、大洋を横断する輸送コンテナの利用を最適化する最善の方法は何だろうか?量子コンピューティングは、これらの充足可能性問題を定義し、グローバーの探索アルゴリズムを使って実装した場合、古典的なコンピューティングに比べて2次的なスピードアップを提供する。

カックロのパズル

SAT問題の面白い例として、Classiq Coding Competitionの問題のひとつである「カックロ」がある。カックロは数独やクロスワードパズルに似た論理パズルである。目標は、各行と各列の内容が指定された合計になるように、そして行や列の2つのセルの番号が同じにならないように、空白のセルを数字で埋めることである。競技会では、回路を単一量子ビットユニタリゲートとCXゲートに分解した後、オラクルで最も少ないCXゲートでグローバー探索を使って以下のパズルを解くという問題が出された。

このパズルを手作業で解き始めると、ゲームのルールはオラクルが解くためのブーリアンロジックで書けることがわかる。X5とX6は足して1、X4とX6は足して1、といった具合だ。ルール間の重複に気づいた後、私たちはそれらを符号化する単純化された制約のリストを定義しました。これらの制約がどのように削減されたかについては、こちらを参照してください。以下が満たすべき制約です。


"(x0 != x1)と" 
"(x2 + 2 != x3)と" 
"(x3 != x4) と" 
"(x1 != x3)と"
"(x3 != x5)と"  
"(x5 != x6)と" 
"(x0 != x2)と"
"(x1 != x5)と" 
"(x4 != x6)と" 
"(x3 == 2)と" 
"(x2 + x4 + x3 == 3)"

ClassiqでKakuroを解く方法

このノートではClassiqのPython SDKを使って問題を解いていきますが、すべての結果はVisual Studio CodeのClassiqエクステンションでも実現できます。ClassiqのPython SDKを使ってこの問題を解くには、組み込みの算術関数の中で制約を式として定義するだけです。変数をシングル量子ビット・レジスタとして宣言しますが、X3はダブル量子ビット・レジスタ(0, 1, 2, 3の値を取ることができるため)として宣言します。 


from classiq import ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic.
from classiq.interface.generator.model import Constraints, Preferences.
from classiq.interface.generator.model.preferences.preferences import (
    CustomHardwareSettings、
)

EXPRESSION = "(x0 != x1) and".+ \
             "(x2 + 2 != x3) and "+ \
             "(x3 != x4)と" + \
             "(x3 != x1)と" + \
             "(x5 != x6) and "+ \
             "(x0!=x2)と" + \+ \
             "(x1 != x5)と" + \+ \
             "(x4 != x6) and "+ \
             "(x3 == 2)と"+ \
             "(((x2 + x4) + x3)%4 == 3)"


oracle_params = 算術式(
    expression=EXPRESSION、
    定義=dict(
        x0=RegisterUserInput(size=1)、
        x1=RegisterUserInput(size=1)、
        x2=RegisterUserInput(size=1)、
        x3=RegisterUserInput(size=2)、
        x4=RegisterUserInput(size=1)、
        x5=RegisterUserInput(size=1)、
        x6=RegisterUserInput(size=1)
    ),
    uncomputation_method="naive"、
)

次に、ハードウェア設定を指定し、CXゲートとUゲートの基本ゲート・セットを宣言する。最後に、CXゲート数を最適化し、回路を合成する。



custom_hardware_settings = CustomHardwareSettings(basis_gates=["cx", "u"])
preferences = Preferences(custom_hardware_settings=custom_hardware_settings)

model_designer = ModelDesigner(constraints=Constraints(optimization_parameter='cx'), preferences=preferences)
model_designer.Arithmetic(params=oracle_params)

circuit = model_designer.synthesize()

circuit.show_interactive()
print(f"{circuit.transpiled_circuit.depth=}")
print(f"{circuit.transpiled_circuit.count_ops['cx']=}")

このコードを実行すると、Classiqの合成エンジンはさまざまな最適化手法を数秒以内に検討し、目的の機能を満たす回路を返します。以下に示す対話型回路と、その結果の深さとCXゲート数を示します


circuit.transpiled_circuit.depth=197
circuit.transpiled_circuit.count_ops['cx']=190

インタラクティブ・ビジュアライゼーション

クラシックのロゴ

スクリプトにエラーがありました

1ヵ月間にわたるコンペティションで選手たちが作成した他のソリューションは、こちらをクリックしてご覧ください。

パズルを超えて

Classiqプラットフォームを使えば、より高度なSAT問題も解くことができます。量子コンピュータが実世界の価値を生み出すには、数百から数千の量子ビットが必要になると予測されており、Classiqは将来の大規模回路にも対応しています。次のコードブロックは10変数、100節のオラクルから 715量子ビットの回路を合成しています。


from classiq import ModelDesigner
from classiq.interface.generator.arith.arithmetic import RegisterUserInput, Arithmetic

EXPRESSION = "(((x0 または ~x1 または ~x8) and (~x7 または ~x5 または ~x6)) and ((~x4 または ~x3 または ~x0) and (x0 または x3 または x7)) and ((~x5 または x0 または ~x2) and (x0 または ~x7 または ~x9))".~x2)と((x0 または ~x7 または ~x9))と((~x5 または x4 または x6)と((x4 または ~x8 または x9))と((x6 または ~x5 または ~x7)と((x8 または ~x6 または ~x4)))と"+ \
             "(((x5または~x3または~x7)および(x7または~x1または~x4))および((~x5または~x6または~x2)および(~x8または~x0または~x4))および((x4または~x8または~x5))と((~x0 or x6 or ~x7))と((x4 or x2 or ~x8)と((~x6 or ~x9 or x0))と((x9 or ~x0 or x7)と((~x7 or x5 or ~x9)))と"+ \
             "(((x6または~x0または~x9)および(x5または~x8または~x1))および((x3または~x6または~x2)および(x7または~x5または~x8))および((x8または~x6または~x3)および(x3または~x1または~x4))と((~x3または~x9または~x4)と((~x8または~x1または~x4))と((~x6または~x3または~x9)と((~x4または~x6または~x3)))とがある。+ \
             "(((~x0 or x8 or x5) and (~x6 or x7 or ~x4)) and ((x9 or ~x8 or ~x4) and (~x4 or x2 or ~x0)) and ((x7 or x6 or ~x5))と((x7又は~x2又は~x8))と((x5又は~x6又は~x7)と((~x2又は~x3又は~x0))と((x2又は~x3又は~x5)と((~x3又は~x8又は~x5))と"+ \
             "(((x6 または ~x1 または ~x9) および (~x0 または ~x1 または x4)) および ((x3 または x7 または ~x2) および (x4 または x2 または ~x0)) および ((~x0 または ~x5 または x4) および(~x3または~x7または~x1))と((~x0または~x3または~x7)と((~x9または~x5または~x8))と((~x6または~x7または~x0)と((~x6または~x1または~x8)))とがある。+ \
             「(((x8または~x4またはx1)および(x4またはx2または~x3))および((~x0または~x2または~x5)および(~x0または~x8または~x4))および((~x6または~x9または~x0)))と((x4 or x0 or x9))と((x8 or ~x7 or x9)と((x0 or ~x1 or ~x2))と((~x7 or x2 or x5)と((x6 or x8 or x3)))と"+ \
             "(((~x4またはx6またはx8)および(x9または~x6または~x4))および((~x9または~x6またはx2)および(~x2またはx7またはx6))および((x3または~x9またはx1)および(x8または~x7または~x9))と((x2または~x1またはx0)と((x2または~x6または~x4))と((~x3または~x6または~x8)と((~x0または~x4またはx2)))とがある。+ \
             "(((x2または~x0またはx8)および(~x8または~x5または~x9))および((x5または~x8または~x9)および(x1または~x3または~x0))および((~x6または~x9または~x7))と((~x9 or x1 or x2))と((x0 or ~x1 or ~x8)と((x8 or ~x6 or x3))と((~x8 or x1 or ~x2)と((x4 or ~x1 or x0)))と"+ \
             "(((x9 または x3 または ~x0) および (x5 または ~x9 または x2)) および ((~x0 または x5 または ~x9) および (x1 または x8 または ~x5)) および ((~x7 または ~x0 または x4) および(~x1または~x7または~x5))と((x8または~x0または~x6)と(~x7または~x5または~x9))と((x5または~x6または~x8)と(~x6または~x9または~x3)))と"+ \
             "(((~x9 or ~x1 or x3) and (x2 or ~x5 or ~x6)) and ((~x2 or x1 or ~x4) and (x0 or x8 or ~x9)) and ((~x4 or x1 or x7))および((x8または~x4または~x0))および((x1または~x0または~x4)および((~x9または~x8または~x1))および((~x5または~x1または~x8)および((~x4または~x3または~x8)))")



oracle_params = 算術式(
    expression=EXPRESSION、
    定義=dict(
        x0=RegisterUserInput(size=1)、
        x1=RegisterUserInput(size=1)、
        x2=RegisterUserInput(size=1)、
        x3=RegisterUserInput(size=1)、
        x4=RegisterUserInput(size=1)、
        x5=RegisterUserInput(size=1)、
        x6=RegisterUserInput(size=1)、
        x7=RegisterUserInput(size=1)、
        x8=RegisterUserInput(size=1)、
        x9=RegisterUserInput(size=1)、
    ),
    uncomputation_method="naive"、
)

model_designer = ModelDesigner()
model_designer.Arithmetic(params=oracle_params)

circuit = model_designer.synthesize()

circuit.show_interactive()

このコードで生成された 715量子ビットのインタラクティブ回路はこちらで見ることができる。

また、生成された回路を量子クラウド・サービス上に展開することも難しくない。例えば、Classiqプラットフォームで解いたSAT問題をAmazon Braket上で実行した詳細な例をご覧ください。 

最終的には、量子コンピューターはロジックパズルや単純な演算のためだけに使われることはないだろう。量子コンピューターが提供する利点は、検索(グローバーのアルゴリズムでSAT問題を解く)、パターン認識(量子機械学習)、最適化(古典と量子のハイブリッドQAOA)など、大規模なデータセットを扱うあらゆる産業で、これまでよりもはるかに高速に活用されるようになるだろう。量子を探求するコストは低く、それを無視すると壊滅的な打撃を受ける可能性があるため、量子コンピューティングはテクノロジーの未来にとって最大の保険のひとつとなる。Classiqのプラットフォームは、量子のユースケースに興味がある方にも、量子コードをより高いレベルに引き上げたい方にも、専門的な知識を提供します。 

Classiqと革新的なソフトウェアの詳細については、こちらからお問い合わせください。

"キュービット・ガイのポッドキャスト "について

The Qubit Guy(弊社最高マーケティング責任者ユヴァル・ボーガー)がホストを務めるこのポッドキャストは、量子コンピューティングのオピニオンリーダーをゲストに迎え、量子コンピューティングエコシステムに影響を与えるビジネスや技術的な疑問について議論します。ゲストは、量子コンピュータのソフトウェアやアルゴリズム、量子コンピュータのハードウェア、量子コンピューティングの主要なアプリケーション、量子産業の市場調査などについて興味深い見解を提供します。

ポッドキャストへのゲスト推薦をご希望の方は、こちらまでご連絡ください。

量子ソフトウェア開発を開始

お問い合わせ