"External component has thrown an exception." for SudokuGrover running 4x4-classic about quantum HOT 5 CLOSED

Yes, this definitely is a memory issue. The sudoku puzzle in this example has 8 missing digits, with 2 bits per digit the algorithm will need 16 qubits to represent the search space alone. With the extra qubits allocated during the execution to check the constraints, one per constraint, the number of qubits used in the oracle implementation is over 50, which is a lot more than the simulator can handle. The hardcoded examples used with the quantum solution have fewer missing digits and fewer constraints, so they don't run in a similar memory issue.

It would make sense to update this example to add some checks on the total number of qubits that will be used, and to fail early with a cleaner error message when the number of qubits is over 30. @cgranade, what do you think?

from quantum.

Thanks @tcNickolas. this is what i suspected too. I wonder if there is an additional way to address some of these kinds of situations. It occurs to me that the number of starting constraints + number of possible values = size (e.g., 4 for a 4x4, 9 for a 9x9 puzzle) * empty vertices. So, in the case I outlined above, there are 8 vertices which equate to 32 values all in all; 22 starting number constraints are known...leaving a total of ten possible values left for the 8 vertices (6 have 1 possible value and 2 have 2 each). In the case where starting constraints is greater than 1/2 * empty vertices * size, could the puzzle be solved with possible values instead of starting constraints? In this case, it would use 10 instead of 22..

I've played around with this and I think it would need something similar to the ConstrainByEdgeAndStartingColors function but for PossibleValues instead of constraints. Instead of checking if the numbers are the same, it would check to see if the value is one of the possible values; like an == (1 OR 3). I think it would replace these lines of code

  for ((cell, value), conflictQubit) in Zipped(startingColorConstraints, startingColorConflictQubits) {
            // Check that cell does not clash with starting colors.
            ControlledOnInt(value, X)(
                colorsRegister[cell * bitsPerColor .. (cell + 1) * bitsPerColor - 1],
                conflictQubit
            );

But I am still coming up to speed with Quantum and not sure what the code would look like (or if its even possible) to change the conflictQubit based on whether the value is equal to a set of possible values.

thanks again for your help

from quantum.

I finally had the time to dig into this question, and this optimization alone, while reducing the number of qubits necessary to evaluate the same constraints, doesn't bring it down enough to solve your puzzle. I had to do something cleverer, incorporate this type of constraints into the search space construction (prep of the initial state and the reflection about the mean step) so as to avoid checking them as constraints at all. I even wrote a blog post about this!

@msoeken, @cgranade - does it make sense to bring those optimizations into our official sample, so that it could solve larger and more interesting puzzles?

from quantum.

yes, i tried it out and you are correct - it doesnt bring it down enough. I have other ideas (intersections of rows, columns, blocks) but got pulled into other work and havent been able to look at this in a bit. i plan to try some other thoughts when i get time again

BTW, i didnt know about this blog post. I love it! Thank you for writing it!!

from quantum.

You couldn't have known about the blog post, I've published it less than 12 hours ago :-)

from quantum.