Generating a 715-Qubit Circuit and Solving Other SAT Problems with Classiq

This note describes how to use the Classiq platform to solve constraint satisfaction problems, including Kakuro — one problem from our recent Coding Competition. Then, it demonstrates a much more complex example that generates a circuit for 715 qubits.

We Live in a Constrained World

Constraint satisfiability (SAT) problems are everywhere. This difficult class of problems is so far-reaching that there exists an international conference aimed at defining and solving specific cases, with applications such as “Formal Verification, Artificial Intelligence, Operations Research, Computational Biology, Cryptography, Data Mining, Machine Learning, Mathematics, etc.” In every industry, there lies some constraint. Take logistics, for example — applicable to any industry with complex moving parts. The packing of products in a limited volume is just one case of a constraint satisfiability problem, and it’s easy to imagine how fast these problems become impossible to solve. One human can configure a car of luggage, and one team can arrange a closet of supplies, but what’s the best way to optimize the utilization of trans-oceanic shipping containers? Quantum computing offers a quadratic speedup to classical computing when these satisfiability problems are defined and implemented using Grover’s Search Algorithm.

The Kakuro Puzzle

An interesting example of a SAT problem is Kakuro, which was one problem in the Classiq Coding Competition. Kakuro is a logic puzzle similar to Sudoku or a crossword puzzle. The goal is to fill in the empty cells with numbers such that the contents of each row and column add to a specified sum and no two cell numbers in a row or column are the same. For the competition, the problem was to solve the following puzzle using a Grover Search with the fewest CX gates in the oracle after decomposing the circuit into single-qubit unitary gates and CX gates.

‍Continue reading the full post, including the code and interactive quantum circuits here

Originally published at https://www.classiq.io.