1
$\begingroup$

I've been learning about quantum computing, and I noticed that another way to describe the state vector is as a path in a binary tree where each level of tree represents another qubit, each node represents a state, and the edge weights represent the probability amplitude of moving from one state to another. Here's an example: (Sorry for MS Paint!)

Binary Tree State Vector

Now what's interesting is that if you start with a state vector of |0>, placing qubits into superposition opens paths in the tree, while entanglement and "measurement" close paths. I was working this out with the sudoku example in the qiskit textbook at Qiskit Grover's Algorithm Example, and I found that if you adhere to the following principles, you can find the solution state while avoiding false paths in the tree just by following the quantum circuit:

  1. Start with a linear tree with every bit in the 0 state.
  2. Place a single variable qubit into superposition, creating a single sub-tree/branch.
  3. Apply all CNOT gates related to that qubit to close off any potential branching and adjust the states of the nodes appropriately.
  4. Whenever a "clause bit" (as described in the link above) no longer has any more gates attached to it, or is no longer being interacted with, close all branches where the nodes do not have the "clause bit" in a position of 1.
  5. Place the next variable qubit into superposition and repeat 3 & 4, until all variable qubits have been placed into superposition.

So, the circuit design would look like this (forget about the diffuser and toffoli for the moment):

enter image description here

I did a step-by-step implementation of this in excel, drawing out all of the trees, and I found that only two main sub-trees form (one for each solution) and that at most only four sub-trees/branches are present at any one time. Furthermore, at the end, all of the clause bits were in the state 1. Now considering that there are a total of 8 qubits in this system, a total of 256 different paths are possible. Is this just a trivial example or could this actually be implemented as a viable algorithm for path finding?

enter image description here enter image description here enter image description here

Edit: P.S. Could this answer P = NP? Also I noticed my quantum circuit isn't quite correct.

$\endgroup$
14
  • $\begingroup$ What about measurement? The system will collapse, and you'll only get one of the potential outputs. Is that acceptable? $\endgroup$
    – C. Kang
    Sep 13 '20 at 17:18
  • $\begingroup$ As long as we are only looking for just a solution it should be okay. The way I am looking at this is more from a classical view, where if you were to make a linked list by following the directions of the quantum circuit, you would find a solution out of 2^n possible paths without having to traveling to more than just a few branches before noticing which one leads to a solution or not. The circuit acts as a guide. $\endgroup$
    – skubis17
    Sep 13 '20 at 19:06
  • $\begingroup$ But you would only get one of the answers out, is my core point - quantum is not like a linked list, because all of the amplitudes of the state vector interact with each other. $\endgroup$
    – C. Kang
    Sep 13 '20 at 19:17
  • $\begingroup$ Yes, but I am not suggesting this be used in a quantum system. I am suggesting to use it on a classical system to solve path finding problems. It's just that you actually have to design a quantum circuit in order to be guided down the correct path. I guess my main question is whether or not quantum circuits become too complex as they grow to implement as a path finding algorithm to problems. Take Sudoku for example. If you have a puzzle which has only one solution, the above method should take you to the solution of the puzzle, but how long would it take compared to current methods? $\endgroup$
    – skubis17
    Sep 13 '20 at 19:48
  • 1
    $\begingroup$ Wait, I'm confused - what is the quantum component of the algorithm? It seems like this is a solely classical approach, namely a BST $\endgroup$
    – C. Kang
    Sep 13 '20 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.