BQP Grid-Based Problems
What is BQP?
BQP is a complexity class that specifically works with quantum computation. It consists of problems that can be solved by quantum algorithms, using elementary operations, in polynomial time, with at least 2/3 accuracy. The allowable elementary operations include many of the ones we learned in class, including Hadamard gates, rotation through an angle θ, and controlled unitary operators. The 2/3 accuracy accounts for the inherent randomness associated with measuring a value from a superposition; by repeating an algorithm many times, you can obtain an algorithm with greater accuracy.
The model of quantum computation associated with BQP works based on many of the principles we have covered in 6.S089. The system uses superpositions of states instead of probability distributions of states, and the fact that superpositions have more possible combinations of base states than distributions represents the increased computing power of quantum computers. We covered the universality of quantum gates, which is used here because the sequence of elementary operations we perform during quantum computation must be able to represent any possible series of operators. The system also allows for partial measurement, where we measure just some of the qubits. Our application of Simon’s algorithm in Problem Set 3 uses partial measurement, as we measure several values of z over the course of the algorithm. In addition, Simon’s algorithm has a probabilistic outcome rather than a guaranteed one, as we need our randomly measured values of z to be distinct (and somewhat independent) in order to create a system of equations that uniquely specifies the value of b. The measuring of superpositions in quantum computation has an inherent degree of randomness, which makes BQP, as an analog to the probabilistic complexity class BPP, a good system for measuring the complexity of quantum algorithms.
Simon’s Grid
I have developed a simple grid-based puzzle type called Simon’s Grid based on the problem solved by Simon’s Algorithm. Below is an example puzzle and its solution.
Rules
In Simon’s Grid, solvers are given an n-by-n grid of squares (where n is at least 4) containing some numbers at the intersections of four cells. The goal is to determine the solution to the grid, which consists of determining whether each cell is unshaded (corresponding to the bit 0) or shaded (corresponding to 1). Numbers represent how many of the four surrounding cells are shaded.
Each row r_i and column c_j has a function f_i or g_j satisfying the conditions of Simon’s algorithm where a is the bitstring specified by the solution to the puzzle. More specifically, row r_i has a function f_i on the set of length-n bitstrings satisfying f(x) = f(x+a) for all length-n bitstrings x, where a is the sequence of bits in row r_i in the solution to the puzzle. (The columns are analogous.) At any point, solvers can input a pattern of bits into the grid and are told the values of all of the row and column functions.
Simon’s Grid is in BQP
The proof that Simon’s Grid is in BQP is directly based on Simon’s Algorithm. We can essentially just apply Simon’s Algorithm to each row independently and ignore the puzzle’s column and number constraints. Here is the algorithm:
Suppose that our grid consists of n rows. On each of the n rows of the grid, we run the bitstring-finding part Simon’s algorithm n³ times to obtain a set of bitstrings z_1, …, z_{n³}. If these bitstrings contain a linearly independent set of n-1 bitstrings, we solve the corresponding set of linear equations to determine the solution b_i for that row. If the bitstrings do not contain such a linearly independent set, we return a string of n 0s as the solution for that row.
To show that the problem is in BQP, we need to show that this algorithm runs in polynomial time and that it returns the correct solution with probability at least 2/3. The bitstring-finding part of Simon’s algorithm runs in polynomial time, and we repeat this part of the algorithm n⁴ times (n³ times on each of the n rows), so the algorithm runs in polynomial time.
For correctness, we note that, due to the correctness of Simon’s algorithm, the algorithm will output the correct solution if it finds a linearly independent set of bitstrings in each row. We can select a particular basis for each row and determine the probability that all of the bitstrings in this basis are in the n³ selected bitstrings. The probability of not selecting a string at any attempt is at most (n²-1)/(n²), so after running n³ steps, the probability of not finding any specific string is at most ((n²-1)/(n²))^(n³)$. Thus, the probability of finding all n-1 bitstrings in the selected basis for a row is at least 1 minus this probability, and the probability that the basis is found in every row is at least \(1-n((n²-1)/(n²))^(n³))^n. When n = 4, this probability is approximately 0.77, and the probability increases as n increases. Thus, the probability of the algorithm returning the correct solution is at least 2/3, and Simon’s Grid is in BQP.
A More Efficient Algorithm
Our algorithm to show that Simon’s Grid is in BQP doesn’t use column or number constraints. When we consider all of the constraints, we can apply the bitstring-finding section of Simon’s Algorithm to the entire puzzle grid at once. Each application gives a linear equation on the bits of the solution in each row or a linear equation on the bits of the solution in each column, so we can obtain a set of row equations or a set of column equations all at once. When we also consider the given number clues, we obtain a linear programming problem, where we need to satisfy all of the row and column equations while also meeting an upper and lower bound for the number of shaded cells in each of the 2-by-2 boxes identified by a number. It’s harder to set a bound on how many applications of the technique of Simon’s algorithm are necessary to give a linear programming problem that has at least a 2/3 chance of uniquely specifying the solution to the Simon’s Grid puzzle, but it certainly does not exceed the n⁴ applications from the BQP proof, and is likely to be much lower.
Further Work
Here are some further areas of research:
Create an interface in which players can attempt to solve Simon’s Grid puzzles. This interface seems interesting to design in that players need to compile and analyze many equations on the bits of the solution based on the row and column functions, and a good interface should provide a natural system for working with this information.
Implement the BQP algorithm or the linear programming algorithm for solving Simon’s Grid problems.
Determine alternate interior clues, besides 2x2-box numbers, that would create interesting logic. In particular, the numbers presented in Simon’s Grid only give information relating adjacent rows and columns, so it may be interesting to consider clues that give information relating rows and columns that are further apart.
Works Cited
Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.
Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2), 303–332.
