-
Graph displayed for graph_colorings((0, 1, 2), ((0, 1), (1, 2)), (0, 1, 2), 5)
What it does
Given a graph (nodes, edges, colors) and a number of repetitions n, graph_colorings() outputs the circuit used and the frequencies observed by the simulator. The number of qubits used will equal len(nodes) * ceil(log2(len(colors)) + len(edges) + 1, so to ensure reasonable runtime keep this number below 10.
Important Use Information
Due to the limited time available, there are limits on what functionality has been implemented for nodes and colors. Each must be a tuple/list of consecutive integers starting at 0 (i.e (0, 1, 2, ...)). edges is a tuple of pairs of elements from nodes.
The output
When graph_colorings(nodes, edges, colors, n) is run, the frequencies that the simulator returns for each coloring are displayed in decreasing order. The bars that are colored red are the correct answers, while blue bars are incorrect. The label of the graph shows the percent of simulated runs that returned a correct answer. As mentioned, the function also returns the quantum circuit used and the frequency distribution. The quantum circuit can be viewed using qc.draw().
Plans to take it further
There are a few things I would have liked to implement if I had had more time.
Grover repetition estimator
Each repetition of Grover's Algorithm rotates you through the superposition of all possible answers and each problem has an optimal number of repetitions to approach the superposition of only correct answers which is determined by arcsin(num_solutions / num_possibilities). The current version relies on the user to input the number of repetitions, but by estimating the likely number of solutions for a given graph, I should be able to determine the best number of repetitions to maximize the likelihood of finding a correct answer.
Graph interface
I would like to implement an interface through which the user can create a graph with nodes and colors named however they like, and to display the most frequently observed graph coloring using networkX. I could also make an interface that emulates a Sudoku board.
Gate simplification
It would constitute a significant reduction in calculation time if the circuit builder recognized when a simplification is possible, such as when a gate is followed immediately by its inverse. Currently, there are many instances where an X gate is performed twice on a node in immediate succession, which is a null operation.
Variable color subsets
I would also like to implement the ability to give each node its own subset of colors from which to choose from. One possible application for this is in solving a sudoku puzzle, where specific nodes are already filled in with a single value. In a 9x9 sudoku board, each prefilled node would reduce the number of qubits required by 3. My existing implementation already includes some of the backbone for this but I didn't have time to put it all together.
Multi-sided edges
In order to reduce the number of qubits required, it may be useful to implement edges that connect more than two nodes. These edges would indicate that every node connected in this way has to be colored differently. This again could be useful in sudoku, where instead of creating 36 edges for each row, column, and 3x3 square of the board to indicate that no pair of two nodes in each group can be the same, a single 9-sided edge can be made that indicates that all 9 must be different. This obviously constitutes a significant reduction in qubits required to represent certain graphs. For example, the number of qubits needed to represent an empty 9x9 sudoku board would decrease from 1297 to 352.
Opposite edges
Another possibility is edges that indicate that their nodes must have the same value instead of different values, which would extend the capabilities of the solver to a whole new range of problems.
Resources
Mukherjee, Sayan. “A Grover Search-based Algorithm for the List Coloring Problem.” arxiv:2108.09061v2, 8 Feb. 2022, IEEE, arxiv.org/pdf/2108.09061.pdf
Log in or sign up for Devpost to join the conversation.