Using the QuantumFramework paclet, which is very much in early stages of development. Some features were written specifically to help solve this problem, like boolean oracles and improved Qiskit integration.
In[]:=
PacletInstall["https://wolfr.am/DevWQCF",ForceVersionInstall->True]<<Wolfram`QuantumFramework`
Out[]=
PacletObject
Intro
Intro
The problem:
Kakuro is a logic puzzle, often referred to as a mathematical transliteration of the crossword. The puzzle is played on a grid of filled and empty cells. The filled cells contain the required sum for the matching empty cells.
The objective of the puzzle is to fill the empty spaces under two constraints:
- Two cells on the same row/column cannot have the same number.
- The sum of the cells on each row/column should equal the matching filled cell.
The objective of the puzzle is to fill the empty spaces under two constraints:
- Two cells on the same row/column cannot have the same number.
- The sum of the cells on each row/column should equal the matching filled cell.
In[]:=
mat=
;
x0 | x1 | 0 |
x2 | x3 | x4 |
0 | x5 | x6 |
Manual solution for practice:
In[]:=
sol={x0->2,x1->1,x2->3,x3->2,x4->0,x5->0,x6->1}
Out[]=
{x02,x11,x23,x32,x40,x50,x61}
In[]:=
sol[[All,2]]
Out[]=
{2,1,3,2,0,0,1}
In[]:=
mat/.sol//MatrixForm
Out[]//MatrixForm=
2 | 1 | 0 |
3 | 2 | 0 |
0 | 0 | 1 |
Construct constraints:
In[]:=
constraints=Join[Catenate[Unequal@@@Subsets[DeleteCases[#,0],{2}]&/@mat],Catenate[Unequal@@@Subsets[DeleteCases[#,0],{2}]&/@(mat)],Thread[Plus@@@mat=={3,5,1}],Thread[Plus@@@(mat)=={5,3,1}]]
Out[]=
{x0≠x1,x2≠x3,x2≠x4,x3≠x4,x5≠x6,x0≠x2,x1≠x3,x1≠x5,x3≠x5,x4≠x6,x0+x13,x2+x3+x45,x5+x61,x0+x25,x1+x3+x53,x4+x61}
Allowed simplification
Out[]=
(x0 != x1) and |
(x0 != x2) and |
(x1 != x3) and |
(x1 != x5) and |
(x2 + 2 != x3) and |
(x2 + x4 + x3 == 3) |
(x3 == 2) and |
(x3 != x4) and |
(x3 != x5) and |
(x4 != x6) and |
(x5 != x6) and |
x3 = {x3[2], x3[1]}
In[]:=
boolSol=MapAt[ResourceFunction["InverseBoole"],{All,2}]@{x0->0,x1->1,x2->1,x3[1]->0,x3[2]->1,x4->0,x5->0,x6->1}
Out[]=
{x0False,x1True,x2True,x3[1]False,x3[2]True,x4False,x5False,x6True}
Semi-manual constraint construction:
Enumerate cases for x2 + x4 + x3 == 3
In[]:=
Cases[Tuples[{{0,1},{0,1},{0,1,2,3}}],tuple_/;Total[tuple]==3:>ResourceFunction["InverseBoole"]@MapAt[Splice@IntegerDigits[#,2,2]&,tuple,-1]]plusConstraint=Or@@(And@@Thread[Pick[{x2,x4,x3[2],x3[1]},#]]&/@%)
Out[]=
{{False,False,True,True},{False,True,True,False},{True,False,True,False},{True,True,False,True}}
Out[]=
(x3[2]&&x3[1])||(x4&&x3[2])||(x2&&x3[2])||(x2&&x4&&x3[1])
In[]:=
vars={x0,x1,x2,x3[1],x3[2],x4,x5,x6};boolConstraints={(x3[2]&&x3[1])||(x4&&x3[2])||(x2&&x3[2])||(x2&&x4&&x3[1])(*x2+x4+x3==3*),!x2&&(!x3[2]||x3[1])||x2&&(!x3[2]||!x3[1])(*x2+2!=x3*),!x4&&(x3[2]||x3[1])||x4&&(x3[2]||!x3[1])(*x3!=x4*),!x5&&(x3[2]||x3[1])||x5&&(x3[2]||!x3[1])(*x3!=x5*),!x3[1]&&x3[2](*x3==2*),x0!=x1,(*x0!=x1*)x0!=x2,(*x0!=x2*)x1!=x3[1],(*x1!=x3*)x1!=x5,(*x1!=x5*)x4!=x6(*x4!=x6*),x5!=x6(*x5!=x6*)}/.{Unequal[x_,y_]:>BooleanConvert[Not[x⧦y]],Equal[x_,y_]:>BooleanConvert[x⧦y]};
In[]:=
constraintLabels={"x2 + x4 + x3 == 3","x2 + 2 != x3","x3 != x4","x3 != x5","x3 == 2","x0 != x1","x0 != x2","x1 != x3","x1 != x5","x4 != x6","x5 != x6"};
In[]:=
And@@boolConstraints/.boolSol
Out[]=
True
Enumerate all, only single solution should satisfy all the constraints:
In[]:=
If[And@@boolConstraints/.Thread[vars->#],Thread[vars->Boole@#],Nothing]&/@Tuples[{False,True},Length[vars]]
Out[]=
{{x00,x11,x21,x3[1]0,x3[2]1,x40,x50,x61}}
Classical solver:
In[]:=
SatisfiabilityInstances[And@@boolConstraints,vars,All]
Out[]=
{{False,True,True,False,True,False,False,True}}
Circuit construction
Circuit construction
Construct BooleanOracles for each individual constraint, putting each result on a separate ancilla:
In[]:=
oracle0=QuantumCircuitOperator[MapIndexed[QuantumCircuitOperator[{"BooleanOracle",#,vars,Length[vars]+First[#2]},constraintLabels[[First@#2]]]&,boolConstraints]];
In[]:=
oracle0["Diagram"]
Out[]=
BooleanOracleR decomposes RZ(π) or RY(π) in place of an X with Gray Code Decomposition https://arxiv.org/pdf/quant-ph/0404089.pdf
Counting gates by arity:
84 CNOTs.
Define V-chain from Qiskit:
Try decomposing every MCX gate into a V-chain for comparison:
The BooleanOracleR is much better... 84 is the final CNOT count without MCX
Going to use V-chain for the final MCX over 11 constraints with 60 CNOTs”
Grover
Grover
Smaller test first:
Test Grover circuit with oracle over 4 variables, 5 constraints and 2 solutions:
V-chain version:
Initial state with 3 ancillas, which are not in superposition:
Solutions are nicely recognisable after 2 iterations:
Qiskit simulation for V-chain version:
Big circuit now (8 variables, 11 constraints, 1 solution):
First without decomposition with just BooleanOracle.
Only gates corresponding to constraints (using RY(π) instead of a usual NOT):
Adding Hadamards and MCX:
The following runs slowly...
Test oracle:
Diffuse two times:
Some optimised way to get just probabilities without QuantumMeasurement:
The solution has the highest probability as expected.
Decomposed oracle with BooleanOracleR.
Not running it on any state, just confirming gate equality to the undecomposed version:
Replacing last MCXGate with V-chain to make the final oracle:
V-chain adds 9 additional ancillas:
Final CNOT tally:
Qiskit simulation (without V-chain):
Initialization should put oracle qubits into a superposition and reflect phase for the target qubit:
Applying three times and measure:
Saving QASM with decomposed diffusion for testing, otherwise Qiskit complains on importing it back for some reason (seems like a bug):
The simulation result:
Built-in circuit evaluation:
Stats
Stats
Some success rate stats for more Grover steps:
Running the same simulation for the oracle with resetting yields better success probabilities without zig-zagging, but it’s not about accuracy, it’s about CNOT count :)
Final circuit
Final circuit
Final circuit for three diffusion steps with measurement:
Generate QASM:
Submission
Submission
144 CNOT gates = 84 (11 constraints) + 60 (MCX11 V-chain)
Gray Code Decomposition for each of 11 constraints: 32+8+8+8+4+4+4+4+4+4+4 = 84 CNOTS
Final conjugation with MCX using V-chain: 60 CNOTs
Notebook with explanation, verification, generation, etc.:
https://www.wolframcloud.com/obj/nikm/Published/KakuroFinal.nb
Final conjugation with MCX using V-chain: 60 CNOTs
Notebook with explanation, verification, generation, etc.:
https://www.wolframcloud.com/obj/nikm/Published/KakuroFinal.nb
Python code for testing QASM:
In[]:=
from qiskit import QuantumCircuit
from qiskit import Aer
backend = Aer.get_backend('qasm_simulator')
qc = QuantumCircuit.from_qasm_file(<* NotebookDirectory[] *> + 'kakuro.qasm')
print(qc.count_ops())
result = backend.run(qc).result()
result.get_counts()
from qiskit import Aer
backend = Aer.get_backend('qasm_simulator')
qc = QuantumCircuit.from_qasm_file(<* NotebookDirectory[] *> + 'kakuro.qasm')
print(qc.count_ops())
result = backend.run(qc).result()
result.get_counts()
Strangely bad results, but acceptable :)
For better results the whole oracle must be reset, including V-chain with its ancillas, but doubling CNOT count for that is not justified enough hah