Source code for qrisp.algorithms.quantum_backtracking.backtracking_tree

"""
\********************************************************************************
* Copyright (c) 2023 the Qrisp authors
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License 2.0 which is available at
* http://www.eclipse.org/legal/epl-2.0.
*
* This Source Code may also be made available under the following Secondary
* Licenses when the conditions for such availability set forth in the Eclipse
* Public License, v. 2.0 are satisfied: GNU General Public License, version 2
* with the GNU Classpath Exception which is
* available at https://www.gnu.org/software/classpath/license.html.
*
* SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
********************************************************************************/
"""

from itertools import product

import numpy as np
import networkx as nx
from sympy.physics.quantum import Ket, OrthogonalKet

from qrisp import (QuantumFloat, QuantumBool, QuantumArray, mcz, cx, h, ry, swap, QFT,
                   auto_uncompute, invert, control, IterationEnvironment, bin_rep,
                   cyclic_shift, multi_measurement, increment, xxyy, p, QuantumVariable, cz,
                   mcx, z, x, RYGate, HGate, s, t, s_dg, t_dg)

"""
As specified in the paper (https://arxiv.org/abs/1509.02374), the key challenge
in implementing the quantum backtracking algorithm is the realization of the operators
R_A and R_B. These operators consists of the direct sum of diffuser operators D_x,
where x is an arbitrary node of the backtracking graph.
R_A and R_B are defined as the direct sum of these

R_A = [direct sum] D_x  [summed over all nodes x with even depth]
R_B = |r><r| [direct sum] D_x [summed over all nodes x with even depth]

Or in words: Each node x together with it's children {y : x->y}
defines a subspace H_x = span(|x>, {|y>, x->y}) on which the operator D_x is acting
in-place.

The definition of the D_x operators consists of multiple conditions:

    1. If x is an "accept" node, D_x = 1 (ie. the identity)
    2. If x is the root D_x = 1 - 2|psi_r><psi_r|
        Where |psi_r> = (1+d_r*n)**-0.5 * (|r> + n**0.5 * [sum] |y>)
        Where d_r is  the degree of the root, n is the maximum depth of the tree
        and the sum iterates over all children of r
    3. Otherwise: D_x = 1 - 2 |psi_x><psi_x|
        Where |psi_x> = (d_x)**-0.5 (|x> + [sum] |y>)
        Where d_x is the degree of x and the sum iterates over all children of x

To implement this operator, we will rewrite it a bit:

D_x = 1 - (1+(-1)**accept(x)) * |psi_r><psi_r|

The next step is to assume an operator U_x, which prepares |psi_x> from x

|psi_x> = U_x |x>

We can then write

D_x = D_x = 1 - (1+(-1)**accept(x)) * |psi_r><psi_r|
    = U_x (1 - (1+(-1)**accept(x))*|x><x|) U_x^(-1)

If we pick an encoding, where each node state |x> is a computational basis state,
the center bracket (1 - (1+(-1)**accept(x))*|x><x|) can be realized as a
Z-gate on the bitstring on the
result of accept(x).

Furthermore we need to make sure that only the phase of |x> is flipped. If we simply
apply a Z-gate onto the result of accept, we could also flip the phase of a 
child node y with accept(y) = True. We remedy this problem by determining wether
|x> is odd into a qubit called oddity. For the even diffusing function, this qubit
needs to be in the False state, for the odd function this qubit needs to be in the
True state.

This qubit is then used in a CZ gate.

D_x = U_x CZ(accept(x), oddity(x)) U_x^(-1)

The operator U_x is implemented as the function psi_prep below.

The operator D_x is implemented as the method qstep_diffuser of the
QuantumBacktrackingTree class.

The next layer of complexity is the reject function.
If a node is rejected, it has no children, ie. |psi_x> = |x>.

This could be realized by modifiying the operator U_x but as it turns out there is
a more efficient possibility.

For this consider the fact that for a rejected node

D_x = 1 - 2 |psi_x><psi_x| = 1 - 2 |x><x|

The algorithm will however never evaluate this operator on any of the children of x
so restricted on H_x we can assume

D_x = -1

We therfore now need to modify D_x such that D_x = -1 when reject(x) is True.

To achieve this we deploy a circuit that integrates with our previous construction
but instead performs 

D_x = U_x (-1) U_x^(-1)

if reject(x) = True.

Our goal is therefore now to find some operator O such that

CZ(accept(x), oddity(x)) O(x) = [-1 if reject(x) is True] 
                                        [CZ(accept(x), oddity(x)) if reject(x) is False]
                                        
We conclude that O(reject(x)) needs to flip the phases of all the (pseudo) child states.
(because H_x = span(|x>, {|y>, x->y})).

Similar to the above approach we reuse the oddity qubit to make sure we only operate
on the child states.

Unfortunately we can't assume that the reject function also returns True on the children,
therefore we "lift" the state. This means that we evaluate the reject function on the 
parent. We denote this with the symbol ^.

We conclude:
    
O(x) = CZ(reject(x^), not oddity(x))

To understand how the lifting works, please check the implementation of qstep_diffuser.


This brings us to another important point in the implementation of the algorithm:
The encoding of the node states.

In principle, the paper makes no statement how such an encoding could be realized.
The approach we took here is the following:

A node state |x> is specified by:
    1. A one-hot encoded integer h (for height), which specifies the distance of 
        x from the the steepest leaf.
    2. A QuantumArray branch_qa, which specifies the path to take to reach x.

A few things have to be said about this encoding:

We choose to encoded the height instead of the distance of the root 
(as described in the paper), as this allows straight forward generation of subtrees. 
A node which has height 4 in a some tree T, still has height 4 in a subtree of T.

The initial state of branch_qa is |0>|0>|0>...

Because we use the height instead of the path length, the path to the node is 
specified by the reveresed array. Ie. the path [1,1,0,1]  in a depth 7 tree is 
specified by the branch_qa state

|0>|0>|0>|1>|0>|1>|1>

Any state where there is a non-zero state at an index lower than h is considered
"non-algorithmic", ie. the state does not represent a node. An example could be

h = |4>
branch_qa = |0>|0>|1>|0>|0>|0>
"""


[docs] class QuantumBacktrackingTree: r""" This class describes the central data structure to run backtracking algorithms in a quantum setting. `Backtracking algorithms <https://en.wikipedia.org/wiki/Backtracking>`_ are a very general class of algorithms which cover many problems of combinatorial optimization such as 3-SAT or TSP. Backtracking algorithms can be put into a very general form. Given is a maximum recursion depth, two functions called ``accept``/``reject`` and the set of possible assignments for an iterable x. :: from problem import accept, reject, max_depth, assignments def backtracking(x): if accept(x): return x if reject(x) or len(x) == max_depth: return None for j in assigments: y = list(x) y.append(j) res = backtracking(y) if res is not None: return res The power of these algorithms lies in the fact that they can quickly discard large parts of the potential solution space by using the reject function to cancel the recursion. Compared to an unstructured search, where only the accept function is available, this can significantly cut the required resources. The quantum algorithm for solving these problems has been `proposed by Ashley Montanaro <https://arxiv.org/abs/1509.02374>`_ and yields a 1 to 1 correspondence between an arbitrary classical backtracking algorithm and it's quantum equivalent. The quantum version achieves a quadratic speed up over the classical one. The algorithm is based on performing quantum phase estimation on a quantum walk operator, which traverses the backtracking tree. The core algorithm returns "Node exists" if the 0 component of the quantum phase estimation result has a higher probability then 3/8 = 0.375. Similar to the classical version, for the Qrisp implementation of this quantum algorithm, a backtracking problem is specified by a maximum recursion depth and two functions, each returning a :ref:`QuantumBool` respectively: **accept**: Is the function that returns True, if called on a node, satisfying the specifications. **reject**: Is the function that returns True, if called on a node, representing a branch that should no longer be considered. Furthermore required is a :ref:`QuantumVariable` that specifies the branches that can be taken by the algorithm at each node. **Node encoding** An important aspect of this algorithm is the node encoding. In Montanaros paper a central quantity is the distance from the root $l(x)$. This however doesn't generalize well to the specification of subtrees, which is why we encode the height of a node. For example in a tree with maximum depth $n$ a leaf has height 0 and the root has height $n$. This quantity is encoded as a one-hot integer QuantumVariable, which can be found under the attribute ``h``. To fully identify a node, we also need to specify the path to take starting at the root. This path is encoded in a :ref:`QuantumArray`, which can be found under the attribute ``branch_qa``. To fit into the setting of height encoding, this array contains the reversed path. We summarize the encoding by giving an example: In a binary tree with depth 5, the node that has the path from the root [1,1] is encoded by .. math:: \begin{align} \ket{\text{branch_qa}} &= \ket{0}\ket{0}\ket{0}\ket{1}\ket{1}\\ \ket{\text{h}} &= \ket{3} = \ket{00010}\\ \ket{x} &= \ket{\text{branch_qa}}\ket{\text{h}} \end{align} **Details on the predicate functions** The predicate functions ``accept`` and ``reject`` must meet certain conditions for the algorithm to function properly: * Both functions have to return a :ref:`QuantumBool`. * Both functions must not change the state of the tree. * Both functions must delete/uncompute all temporarily created QuantumVariables. * ``accept`` and ``reject`` must never return ``True`` on the same node. The ``subspace_optimization`` keyword enables a significant optimization of the ``quantum_step`` function. This keyword can be set to True if the ``reject`` function is guaranteed to return the value ``reject(x)`` also on the non-algorithmic subspace of x. For instance, if x = [0,0,1] in a depth 4 tree, the encoded state is .. math:: \begin{align} \ket{\text{branch_qa}} &= \ket{0}\ket{1}\ket{0}\ket{0}\\ \ket{\text{h}} &= \ket{1}\\ \ket{x} &= \ket{\text{branch_qa}}\ket{\text{h}} \end{align} A state from the non-algorithmic subspace of x is now a state that has non-zero entries in ``branch_qa`` at indices less than ``h`` ie. .. math:: \begin{align} \ket{\text{branch_qa}_{NA}} &= \ket{1}\ket{1}\ket{0}\ket{0}\\ \ket{\text{h}} &= \ket{1}\\ \ket{\tilde{x}} &= \ket{\text{branch_qa}_{NA}}\ket{\text{h}} \end{align} For the ``subspace_optimization`` to return proper results, the ``reject`` function must therefore satisfy: .. math:: \text{reject}(\ket{x}) = \text{reject}(\ket{\tilde{x}}) .. note:: Many implementations of backtracking also include the possibility for deciding which entries of x to assign based on some user provided heuristic. The quantum version also supports this feature, however it is not yet implemented in Qrisp. Parameters ---------- max_depth : integer The depth of the backtracking tree. branch_qv : QuantumVariable A QuantumVariable representing the possible branches of each node. accept : function A function taking an instance of QuantumBacktrackingTree and returning a QuantumBool, which is ``True``, if called on a satisfying node. reject : function A function taking an instance of QuantumBacktrackingTree and returning a QuantumBool, which is ``True``, if a called on a node where the corresponding branch should no longer be investigated. subspace_optimization : bool, optional If set to ``True``, a significant optimization of the ``quantum_step`` function will be applied. The reject function has to fullfil a certain property for this to yield the correct results. Please check the "Details on the predicate functions" section for more information. The default is ``False``. Attributes ---------- h : :ref:`QuantumFloat` A one hot encoded integer representing the height of the node. The root has ``h = max_depth``, it's children have ``h = max_depth-1`` etc. branch_qa : :ref:`QuantumArray` A QuantumArray representing the path from the root to the current node. The qtype of this QuantumArray is what is been provided as ``branch_qv``. Note that the state of this array is the reversed path, ie. a the node with path ``[1,1,0,1]`` in a depth 7 tree has the state: $\ket{0}\ket{0}\ket{0}\ket{1}\ket{0}\ket{1}\ket{1}$ States that have a non-zero value at entries indexed smaller than ``h``, are considered non-algorithmic and will never be visited (eg. h=3, branch_qa = $\ket{1}\ket{1}\ket{1}\ket{1}$). qs : :ref:`QuantumSession` The QuantumSession of the backtracking tree. max_depth : int An integer specifying the maximum depth of each node. Examples -------- **Checking for the existence of a solution** Even though primary purpose of backtracking algorithms is to find a solution, at the core, Montanaros algorithm only determines solution existence. This can however still be leveraged into a solution finding algorithm. To demonstrate the solution existence functionality, we search the binary tree that consists only of nodes with alternating branching. We accept if we find the node ``[0,0,1]`` (doesn't exist in this tree). For this we first set up the reject condition. :: from qrisp import * @auto_uncompute def reject(tree): oddity = QuantumBool() for i in range(tree.h.size): if i%2: cx(tree.h[i], oddity) parity = QuantumBool() for i in range(tree.branch_qa.size): cx(tree.branch_qa[i], parity) exclude_init = (tree.h < tree.max_depth-1) return exclude_init & (oddity != parity) This function determines first determines the oddity of the height parameter (remember ``tree.h`` has one-hot encoding!). Next the parity of the branching path is evaluated. Parity means "is the amount of ones in the path even or odd". We will reject the node if the oddity of is unequal to the parity and therefore reject any path that took a 1 after it already took a 1 (same for 0). On the root and it's children there will be rejection to allow for two different paths. We now implement the accept condition: :: @auto_uncompute def accept(tree): height_condition = (tree.h == 0) path_condition = QuantumBool() mcx(tree.branch_qa[::-1], path_condition, ctrl_state = "001") return height_condition & path_condition Subsequently we set up the class instance: :: from qrisp.quantum_backtracking import QuantumBacktrackingTree tree = QuantumBacktrackingTree(max_depth = 3, branch_qv = QuantumFloat(1), accept = accept, reject = reject) tree.init_node([]) We can evaluate the statevector: >>> tree.statevector() 1.0*|[]> The ``[]`` indicates that this is the root state. If the tree was in the state of a child of the root (say the one connected to the 1 branch) it would be ``[1]``. Note that the ``statevector`` method decodes the QuantumVariables holding the node state for convenient readibility. If you want to see the encoded variables you can take a look at the :ref:`QuantumSession` s :meth:`statevector method<qrisp.QuantumSession.statevector>`: >>> tree.qs.statevector() |0>**3*|3> We can also visualize the statevector of the tree: >>> import matplotlib.pyplot as plt >>> tree.visualize_statevector() >>> plt.show() .. image:: ./root_state_plot.png :width: 200 :alt: Root statevector plot :align: left | | | | | And finally evaluate the algorithm: :: qpe_res = tree.estimate_phase(precision = 4) Perform a measurement >>> mes_res = qpe_res.get_measurement() >>> mes_res[0] 0.1036 The 0 component has only 10.36% probability of appearing, therefore we can conclude, that in the specified tree no such node exists. We now perform the same process but with a trivial reject function: :: def reject(tree): return QuantumBool() tree = QuantumBacktrackingTree(max_depth = 3, branch_qv = QuantumFloat(1), accept = accept, reject = reject) tree.init_node([]) qpe_res = tree.estimate_phase(precision = 4) >>> mes_res = qpe_res.get_measurement() >>> mes_res[0] 0.5039 We see a probability of more than 50%, implying a solution exists in this tree. **Finding a solution** Montanaros approach to determine a solution is to classically traverse the tree, by always picking the child node where the quantum algorithm returns "Node exists". Finding a solution can therefore be considered a hybrid algorithm. To demonstrate, we search for the node ``[1,1,1]`` with a trivial reject function. :: @auto_uncompute def accept(tree): height_condition = (tree.h == tree.max_depth - 3) path_condition = QuantumBool() mcx(tree.branch_qa[-3:], path_condition) return height_condition & path_condition def reject(tree): return QuantumBool() Set up the QuantumBacktrackingTree instance: >>> max_depth = 4 >>> tree = QuantumBacktrackingTree(max_depth, branch_qv = QuantumFloat(1), accept = accept, reject = reject) And call the solution finding algorithm: >>> tree.find_solution(precision = 5) [1, 1, 1] **Using the subspace_optimization keyword** To demonstrate the usage of this feature, we create two tree instances - one with and one without the optimization. :: def accept(tree): return QuantumBool() def reject(tree): return QuantumBool() >>> opt_tree = QuantumBacktrackingTree(3, branch_qv = QuantumFloat(1), accept = accept, reject = reject, subspace_optimization = True) >>> no_opt_tree = QuantumBacktrackingTree(3, branch_qv = QuantumFloat(1), accept = accept, reject = reject, subspace_optimization = False) Perform a ``quantum_step`` on both of them: >>> opt_tree.quantum_step() >>> no_opt_tree.quantum_step() And evaluate some benchmarks: >>> no_opt_tree.qs.compile().depth() 89 >>> no_opt_tree.qs.compile().cnot_count() 68 With the optimization these values are much better: >>> opt_tree.qs.compile().depth() 48 >>> opt_tree.qs.compile().cnot_count() 38 """ def __init__(self, max_depth, branch_qv, accept, reject, subspace_optimization = False): self.max_depth = max_depth self.degree = 2**branch_qv.size self.branch_qa = QuantumArray(qtype=branch_qv, shape=max_depth) self.h = OHQInt(max_depth+1, name="h*", qs=self.branch_qa.qs) self.qs = self.h.qs self.accept_function = accept self.reject_function = reject self.subspace_optimization = subspace_optimization def accept(self): return self.accept_function(self) def reject(self): return self.reject_function(self) @auto_uncompute def qstep_diffuser(self, even, ctrl=[], min_height_assumption = 0): """ Performs the operators :math:`R_A` or :math:`R_B`. For more information on these operators check `the paper <https://arxiv.org/abs/1509.02374>`_. Parameters ---------- even : bool Depending on the parameter, the diffuser acts on the subspaces $\mathcal H_x=\{\ket{x}\}\cup\{\ket{y}\,|\,x\\rightarrow y\}$ where $x$ has odd (``even=False``) or even (``even=True``) height. Note that "even" refers to the parity of the ``h`` attribute instead of the distance from the root. If the ``max_depth`` of the tree is odd, and ``even=False`` then $R_A$ (otherwise $R_B$) is performed, and vice verse if the ``max_depth`` is even. ctrl : List[Qubit], optional A list of qubits that allows performant controlling. The default is []. Examples -------- We set up a QuantumBackTrackingTree and perform the diffuser on a marked node :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def reject(tree): return QuantumBool() @auto_uncompute def accept(tree): return (tree.h == 1) tree = QuantumBacktrackingTree(3, QuantumFloat( 1, name = "branch_qf*"), accept, reject) tree.init_node([1,1]) >>> print(tree.qs.statevector()) |0>*|1>**3 >>> tree.qstep_diffuser(even = False) >>> print(tree.qs.statevector()) |0>*|1>**3 We see that the node (as expected) is invariant under :math:`R_A`. """ # This function performs the operation # D_x = U_x (1 - (1+(-1)**accept(x))*|x><x|) U_x^(-1) # For more information, check the beginning of this file # Perform U_x^(-1) with invert(): psi_prep(self, even=even, min_height_assumption = min_height_assumption) # We now perform the operation # 1 - (1+(-1)**accept(x))*|x><x| # by executing an appropriate mcz gate # An additional detail to consider: # We allow for additional control qubits. This is important because # this operator will undergo phase estimation and we want to prevent # performing automatic synthesis of the controlled operation, # as this would imply controlling EVERY gate. Instead we can just # control the mcz gate. # Prepare control state specificator ctrl_state = "" mcz_list = [] # D_x operates on the space span(|x>, {|y>, x->y}) # In order to make sure our mcz gate only marks |x>, we can use the # oddity of h, because if h(x) is odd, then h(y) is not. oddity_qbl = QuantumBool() for i in range(self.max_depth+1): if i < min_height_assumption: continue if bool(i%2) != even: cx(self.h[i], oddity_qbl) ctrl_state += "1" mcz_list.append(oddity_qbl) # Determine accept value accept_value = self.accept() mcz_list.append(accept_value) ctrl_state += "0" # Add additional control qubits mcz_list += ctrl ctrl_state += "1"*len(ctrl) # Perform mcz gate mcz(mcz_list, ctrl_state=ctrl_state) # We now perform the phase-flip on the child states. # For more details why this yields the correct behavior please consult # the text at the beginning of this file. # For this we first have to perform the lifting operation. # Lifting means, that the child states |y> are mapped to their parent. # The first step to achieve this is to swap the branch information # into a temporary container. This way the branching information is 0. # Check if |x> is root. # This if self.max_depth%2 == even: cx(self.h[self.max_depth],oddity_qbl) # Instead of this # is_root = QuantumBool() # cx(self.h[self.max_depth],is_root) temporary_container = self.branch_qa.qtype.duplicate() for i in range(self.max_depth): if i < min_height_assumption or self.subspace_optimization: continue if bool(i%2) == even: with control(self.h[i], ctrl_method = "gray_pt"): swap(temporary_container, self.branch_qa[i]) # The second step is to increment h. Due to the one-hot encoding of h, # we can do this for free with a compiler swap. self.h.reg.insert(0, self.h.reg.pop(-1)) # Determine reject value reject_value = self.reject_function(self) mcz_list = [reject_value] ctrl_state = "1" # Make sure we only apply the phase to the child states (parent states # have oddity 1) mcz_list.append(oddity_qbl) ctrl_state += "0" # Check if |x> is root. Otherwise, if the reject funtions returns "True" on the lift of the root a wrong phase (-1) may be applied to the root. # mcz_list.append(is_root) # ctrl_state += "0" # Add extra controls mcz_list += ctrl ctrl_state += "1"*len(ctrl) #Perform MCZ gate mcz(mcz_list, ctrl_state = ctrl_state) #Reverse compiler swap self.h.reg.append(self.h.reg.pop(0)) #Reintroduce branching information for i in range(self.max_depth): if i < min_height_assumption or self.subspace_optimization: continue if bool(i%2) == even: with control(self.h[i], ctrl_method = "gray_pt_inv"): swap(temporary_container, self.branch_qa[i]) #Delete temporary container. temporary_container.delete() # Perform U_x psi_prep(self, even=even, min_height_assumption = min_height_assumption)
[docs] def quantum_step(self, ctrl=[], min_height_assumption = 0): """ Performs the quantum step operator $R_BR_A$. For more information check the :meth:`diffuser method <qrisp.quantum_backtracking.QuantumBacktrackingTree.qstep_diffuser>`. Parameters ---------- ctrl : List[Qubit], optional A list of qubits, the step operator should be controlled on. The default is []. """ self.qstep_diffuser(even=not self.max_depth % 2, ctrl=ctrl, min_height_assumption = min_height_assumption) self.qstep_diffuser(even=self.max_depth % 2, ctrl=ctrl, min_height_assumption = min_height_assumption - 1)
[docs] def estimate_phase(self, precision): r""" Performs :meth:`quantum phase estimation <qrisp.QPE>` on the :meth:`quantum step operator <qrisp.quantum_backtracking.QuantumBacktrackingTree.quantum_step>`. If executed with sufficient precision, the phase estimation will yield a QuantumFloat, where the probability of the 0 component indicates the presence of a node where the ``accept`` function yielded ``True``. If the probability is higher than 3/8 :math:`\Rightarrow` A solution exists. If the probability is less than 1/4 :math:`\Rightarrow` No solution exists. Otherwise :math:`\Rightarrow` Increase precision. In general, the required precision is proportional to .. math:: \frac{\text{log}_2(Tn)}{2} + \beta Where :math:`T` is the amount of nodes, that would be visited by a classical algorithm, :math:`n` is the maximum depth and :math:`\beta` is a universal constant. Parameters ---------- precision : int The precision to perform the quantum phase estimation with. Returns ------- qpe_res : :ref:`QuantumFloat` The QuantumFloat containing the result of the phase estimation. """ qpe_res = QuantumFloat(precision, -precision, qs = self.qs) h(qpe_res) from qrisp import check_if_fresh if check_if_fresh(self.h.reg[:-1], self.qs): height_tracker = int(self.max_depth) + 1 else: height_tracker = -1 for i in range(qpe_res.size): if height_tracker >= 0 and False: for j in range(2**i): self.quantum_step(ctrl=[qpe_res[i]], min_height_assumption = height_tracker) height_tracker -= 2 else: with IterationEnvironment(self.qs, 2**i, precompile=True): self.quantum_step(ctrl=[qpe_res[i]]) QFT(qpe_res, inv=True) return qpe_res
[docs] def init_phi(self, path): r""" Initializes the normalized version of the state :math:`\ket{\phi}`. .. math:: \ket{\phi} = \sqrt{n}\ket{r} + \sum_{x \neq r, \\ x \rightsquigarrow x_0} (-1)^{l(x)} \ket{x} Where :math:`x \rightsquigarrow x_0` means that :math:`x` is on the path from :math:`r` to :math:`x_0` (including :math:`x_0`). If :math:`x_0` is a marked node, this state is invariant under the quantum step operator. Parameters ---------- path : List The list of branches specifying the path from the root to :math:`x_0`. Examples -------- We set up a backtracking tree of depth 3, where the marked element is the 111 node. :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def reject(tree): return QuantumBool() @auto_uncompute def accept(tree): return (tree.branch_qa[0] == 1) & (tree.branch_qa[1] == 1) & (tree.branch_qa[2] == 1) tree = QuantumBacktrackingTree(3, QuantumFloat( 1, name = "branch_qf*"), accept, reject) Initialize :math:`\ket{\phi}` and evaluate the statevector: >>> tree.init_phi([1,1,1]) >>> print(tree.qs.statevector()) (0.816496014595032*|0>*|1>**3 - 0.816496014595032*|0>**2*|1>*|2> + 1.0*sqrt(2)*|0>**3*|3> - 0.816496014595032*|1>**3*|0>)/2 Perform the quantum step and evaluate the statevector again: >>> tree.quantum_step() >>> print(tree.qs.statevector()) (0.816496014595032*|0>*|1>**3 - 0.816496014595032*|0>**2*|1>*|2> + 1.0*sqrt(2)*|0>**3*|3> - 0.816496014595032*|1>**3*|0>)/2 We see that the node (as expected) is invariant under the quantum step operator. """ h_state = {} h_state[self.max_depth] = (self.max_depth)**0.5 for i in range(1, len(path)+1): h_state[self.max_depth - i] = (-1)**(i) self.h[:] = h_state for i in range(1, len(path)+1): with self.h == self.max_depth - i: for j in range(i): self.branch_qa[-j-1].encode(path[j], permit_dirtyness=True)
[docs] def init_node(self, path): """ Initializes the state of a given node. Parameters ---------- path : List List of the branch labels indicating the path from the root to the node. Examples -------- We initialize a backtracking tree in the 101 node. :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def reject(tree): return QuantumBool() @auto_uncompute def accept(tree): return QuantumBool() tree = QuantumBacktrackingTree(3, QuantumFloat( 1, name = "branch_qf*"), accept, reject) tree.init_node([1,0,1]) """ self.h[:] = self.max_depth - len(path) if len(path): self.branch_qa[-len(path):] = path[::-1]
[docs] def subtree(self, new_root): """ Returns the subtree of a given node. Parameters ---------- new_root : list The path from the root of self to the root of the subtree. Returns ------- QuantumBacktrackingTree The subtree starting at the specified root. Examples -------- We initiate a QuantumBacktrackingTree with trivial reject function and create a subtree starting at an accepted node- :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def accept(tree): height_cond = (tree.h == 2) return height_cond @auto_uncompute def reject(tree): return QuantumBool() Create and initiate the parent tree. >>> depth = 5 >>> tree = QuantumBacktrackingTree(depth, QuantumFloat(1, name = "branch_qf*"), accept, reject) >>> tree.init_node([]) >>> print(accept(tree)) {False: 1.0} We now create the subtree, where the new root has height two, ie. the accept function returns ``True``. >>> subtree = tree.subtree([0,1,0]) >>> subtree.init_node([]) >>> print(accept(subtree)) {True: 1.0} """ return Subtree(self, new_root)
[docs] def copy(self): """ Returns a copy of self. Copy means a QuantumBacktrackingTree with identical depth, accept/reject functions etc. but with freshly allocated QuantumVariables. Returns ------- QuantumBacktrackingTree Another instance with the same depth/accept/reject etc. """ return Subtree(self, [])
[docs] def find_solution(self, precision, cl_accept=None, measurement_kwargs={}): """ Determines a path to a solution. Parameters ---------- precision : integer The precision to perform the quantum phase estimation(s) with. cl_accept : function, optional A classical version of the accept function of self. Needs to receive a list to indicate a path and returns a bool wether the node is accepted. By default, the accept function of self will be evaluated on a simulator. measurement_kwargs : dictionary A dictionary to give keyword arguments that specify how measurements are evaluated. The default is {}. Returns ------- List A list indicating the path to a node where the accept function returns True. Examples -------- We create a accept function that marks the node [0,1] and a trivial reject function. :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat, mcx from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def accept(tree): height_cond = (tree.h == 1) # The [0,1] node has height 1 path_cond = QuantumBool() mcx(list(tree.branch_qa)[1:], path_cond, ctrl_state="10") return path_cond & height_cond @auto_uncompute def reject(tree): return QuantumBool() Create backtracking tree object: >>> depth = 3 >>> tree = QuantumBacktrackingTree(depth, QuantumFloat(1, name = "branch_qf*"), accept, reject) Find solution >>> res = tree.find_solution(4) >>> print(res) [0, 1] """ return find_solution(self, precision, cl_accept, measurement_kwargs=measurement_kwargs)
[docs] def path_decoder(self, h, branch_qa): """ Returns the path representation for a given constellation of the ``h`` and ``branch_qa`` variables. The path representation is a list indicating which branches to take starting from the root. This function exists because the encoding of the nodes is hardware efficient but inconvenient for humans to read. Parameters ---------- h : integer The integer describing the height of the node. branch_qa : list The list of branches to take to reach the root, starting from the node. Returns ------- list The list of path variables to take to reach the node, starting from the root. Examples -------- We create a QuantumBacktrackingTree, initiate a node and retrieve the path. :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat, multi_measurement from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def accept(tree): return QuantumBool() @auto_uncompute def reject(tree): return QuantumBool() >>> depth = 5 >>> tree = QuantumBacktrackingTree(depth, QuantumFloat(1, name = "branch_qf*"), accept, reject) >>> tree.init_node([1,0]) >>> multi_measurement([tree.h, tree.branch_qa]) {(3, OutcomeArray([0, 0, 0, 0, 1])): 1.0} Retrieve the path >>> tree.path_decoder(3, [0, 0, 0, 0, 1]) [1, 0] """ l = self.max_depth - h return list(branch_qa[::-1][:l])
[docs] def statevector_graph(self, return_root=False): r""" Returns a NetworkX Graph representing the quantum state of the backtracking tree. The nodes have an ``amplitude`` attribute, indicating the complex amplitude of that node. Parameters ---------- return_root : bool, optional If set to ``True``, this method will also return the root node. The default is False. Returns ------- networkx.DiGraph A graph representing the statevector. Examples -------- We initialize a backtracking tree, initialize a :math:`\ket{\phi}` state and retrieve the statevector graph. :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def reject(tree): return QuantumBool() @auto_uncompute def accept(tree): return (tree.branch_qa[0] == 1) & (tree.branch_qa[1] == 1) & (tree.branch_qa[2] == 1) Create backtracking tree and initialize :math:`\ket{\phi}`. >>> tree = QuantumBacktrackingTree(3, QuantumFloat(1, name = "branch_qf*"), accept, reject) >>> tree.init_phi([1,1,1]) >>> statevector_graph = tree.statevector_graph() >>> print(statevector_graph.nodes()) [QBTNode(path = [], amplitude = (0.7071066+0j)), QBTNode(path = [0], amplitude = 0j), QBTNode(path = [1], amplitude = (-0.408248-4.4703484e-08j)), QBTNode(path = [0, 0], amplitude = 0j), QBTNode(path = [0, 1], amplitude = 0j), QBTNode(path = [1, 0], amplitude = 0j), QBTNode(path = [1, 1], amplitude = (0.4082481+1.4901161e-08j)), QBTNode(path = [0, 0, 0], amplitude = 0j), QBTNode(path = [0, 0, 1], amplitude = 0j), QBTNode(path = [0, 1, 0], amplitude = 0j), QBTNode(path = [0, 1, 1], amplitude = 0j), QBTNode(path = [1, 0, 0], amplitude = 0j), QBTNode(path = [1, 0, 1], amplitude = 0j), QBTNode(path = [1, 1, 0], amplitude = 0j), QBTNode(path = [1, 1, 1], amplitude = (-0.40824816+5.9604645e-08j))] >>> statevector_graph, root = tree.statevector_graph(return_root = True) >>> print(root) QBTNode(path = [], amplitude = (0.7071066+0j)) """ from networkx import DiGraph sv_function = self.qs.statevector("function") res_graph = DiGraph() root = QBTNode(self, []) root.amplitude = sv_function(root.sv_specifier()) res_graph.add_node(root) last_layer = [root] for i in range(self.max_depth): next_layer = [] for parent_node in last_layer: for j in range(2**self.branch_qa[0].size): child_node_path = list(parent_node.path) + [self.branch_qa[0].decoder(j)] child_node = QBTNode(self, child_node_path) child_node.amplitude = sv_function(child_node.sv_specifier()) res_graph.add_node(child_node) res_graph.add_edge(parent_node, child_node, label=child_node_path[-1]) next_layer.append(child_node) last_layer = next_layer if return_root: return res_graph, root return res_graph
[docs] def visualize_statevector(self, pos=None): """ Visualizes the statevector graph. Parameters ---------- pos : dict, optional A dictionary indicating the positional layout of the nodes. For more information visit `this page <https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw.html>`_ By default is suitable will be generated. Examples -------- We initialize a backtracking tree and visualize: :: from qrisp import auto_uncompute, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree import matplotlib.pyplot as plt @auto_uncompute def reject(tree): return QuantumBool() @auto_uncompute def accept(tree): return (tree.branch_qa[0] == 1) & (tree.branch_qa[1] == 1) & (tree.branch_qa[2] == 1) >>> tree = QuantumBacktrackingTree(3, QuantumFloat(1, name = "branch_qf*"), accept, reject) >>> tree.init_node([]) >>> tree.visualize_statevector() >>> plt.show() .. image:: ./root_state_plot.png :width: 200 :alt: Root statevector plot :align: left >>> tree = tree.copy() >>> tree.init_phi([1,1,1]) >>> tree.visualize_statevector() .. image:: ./phi_state_plot.png :width: 200 :alt: Root statevector plot :align: left """ G, root = self.statevector_graph(return_root = True) def tree_layout(G, node, depth, theta_parent, res_dic={}): r = depth + 1 delta_theta = 2*np.pi/self.degree**(depth+1) theta_start = theta_parent - 2*np.pi/self.degree**(depth)/4 children = list(G.neighbors(node)) for i in range(len(children)): theta = theta_start + i*delta_theta res_dic[children[i]] = (r*np.sin(theta), r*np.cos(theta)) tree_layout(G, children[i], depth+1, theta, res_dic) return res_dic pos= tree_layout(G, root, 0, 0) pos[root]= (0, 0) import colorsys def complex_to_color(cnumber): angle = np.angle(cnumber) radius = np.abs(cnumber) # Normalize the angle to the range [0, 2*pi) angle= (angle + np.pi*5/2) % (2 * np.pi) # Map the angle to the hue component of the color hue = angle / (2*np.pi) # Map the radius to the saturation and value components of the color saturation = 1 value = 1 # Convert the HSV components to RGB hsv_color = (hue, saturation, value) rgb_color = colorsys.hsv_to_rgb(*hsv_color) from scipy.special import expit intensity = expit((radius-0.2)*10) # Convert the RGB components to hexadecimal format hex_color = '#{:02x}{:02x}{:02x}'.format( int(rgb_color[0] * 255*intensity), int(rgb_color[1] * 255*intensity), int(rgb_color[2] * 255*intensity) ) return hex_color colors = [complex_to_color(node.amplitude) for node in G.nodes()] nx.draw(G, pos) nx.draw_networkx_nodes(G, pos, node_color=colors) edge_labels = dict([((n1, n2), l) for n1, n2, l in G.edges(data="label")]) nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=edge_labels)
[docs] def statevector(self): """ Returns a SymPy statevector object representing the state of the tree with decoded node labels. Returns ------- state : sympy.Expr A SymPy quantum state representing the statevector of the tree. Examples -------- We create a QuantumBacktrackingTree with and investigate the action of the :meth:`quantum step diffuser <qrisp.quantum_backtracking.QuantumBacktrackingTree.qstep_diffuser>` :: from qrisp import auto_uncompute, mcx, QuantumBool, QuantumFloat from qrisp.quantum_backtracking import QuantumBacktrackingTree @auto_uncompute def accept(tree): height_cond = (tree.h == 1) # The [0,1] node has height 1 path_cond = QuantumBool() mcx(list(tree.branch_qa)[1:], path_cond, ctrl_state="10") return path_cond & height_cond @auto_uncompute def reject(tree): height_cond = (tree.h == 2) # The [1] node has height 2 path_cond = QuantumBool() mcx(list(tree.branch_qa)[-1], path_cond, ctrl_state="1") return path_cond & height_cond Create tree and initialize a node where neither accept nor reject are True. >>> tree = QuantumBacktrackingTree(3, QuantumFloat(1, name = "branch_qf*"), accept, reject) >>> tree.init_node([0,0]) Evaluate statevector >>> print(tree.statevector()) 1.0*|[0, 0]> >>> tree.qstep_diffuser(even = False) >>> print(tree.statevector()) -0.666660010814667*|[0, 0, 0]> - 0.666660010814667*|[0, 0, 1]> + 0.333330005407333*|[0, 0]> We see that the :meth:`quantum step diffuser <qrisp.quantum_backtracking.QuantumBacktrackingTree.qstep_diffuser>` moves the state to the children of the [0,0] node (ie. [0,0,0] and [0,0,1]). We now investigate how it behaves on nodes that are accepted/rejected: Initiate a new tree >>> tree = tree.copy() >>> tree.init_node([0,1]) >>> tree.qstep_diffuser(even = False) >>> tree.statevector() 1.0*|[0, 1]> As expected, the accepted node is invariant. To investigate the rejected node, we create another copy: >>> tree = tree.copy() >>> tree.init_node([1]) >>> tree.qstep_diffuser(even = True) >>> tree.statevector() -1*|[1]> As expected, the node has eigenvalue -1. If you are unsure why these statevectors are eigenvector please check `the paper <https://arxiv.org/abs/1509.02374>`_. """ sv_function = self.qs.statevector("function", decimals = 10) # Internal qvs are the quantum variables that specify a backtrackingtree node # internal_qvs = [self.h, self.branch_workspace] + list(self.branch_qa) internal_qvs = [self.h] + list(self.branch_qa) # External qvs are any quantum variables that are also registered in the QuantumSession # but don't specify a node external_qvs = list(self.qs.qv_list) # Remove the internal qvs from the external qv_list for qv in internal_qvs: for i in range(len(external_qvs)): if hash(external_qvs[i]) == hash(qv): external_qvs.pop(i) break # Get a list of possible labels for each qv internal_qv_labels = [] for qv in internal_qvs: label_list = [] for i in range(2**qv.size): label_list.append(qv.decoder(i)) internal_qv_labels.append(label_list) external_qv_labels = [] for qv in external_qvs: label_list = [] for i in range(2**qv.size): label_list.append(qv.decoder(i)) external_qv_labels.append(label_list) # This retrieves a list of all possible constellations of labels internal_label_product = list(product(*internal_qv_labels)) external_label_product = list(product(*external_qv_labels)) # This will be the sympy object that is returned res_state = 0 # Go through all internal label consteallations (ie. node states) for internal_label_const in internal_label_product[::-1]: # print(internal_label_const) # Get the path to that node state path = self.path_decoder(internal_label_const[0], internal_label_const[1:]) # print(path) # Create a label dic for the sv_function internal_label_dic= {internal_qvs[i]: internal_label_const[i] for i in range(len(internal_qvs))} # If there are no external qvs, we can simply call the sv_function # with the label dic if len(external_qvs) == 0: amplitude = sv_function(internal_label_dic, 5) if abs(amplitude) < 1E-5: continue # print(res_state) # Add the corresponding ket res_state += np.round(amplitude, 5) * OrthogonalKet(str(path)) # print(res_state) # If there are external qvs we do a similar procedure to go through # all label constellations else: for external_label_const in external_label_product: # Set up the external label dic external_label_dic= {external_qvs[i]: external_label_const[i] for i in range(len(external_qvs))} # Integrate the internal label dic external_label_dic.update(internal_label_dic) # Retrieve the amplitude amplitude = sv_function(external_label_dic) if abs(amplitude) < 1E-5: continue external_ket_expr = 1 # Generate the ket expression for the external qvs for label in external_label_const: external_ket_expr *= OrthogonalKet(label) # Add the corresponding state res_state += amplitude * \ OrthogonalKet(str(path)) * external_ket_expr return res_state
class OHQInt(QuantumVariable): def decoder(self, i): # One hot encoding: # Red: [1,0,0,0] # Green: [0,1,0,0] # Yellow:[0,0,1,0] # Blue: [0,0,0,1] # [0,0,0,1][0,0,1,0] # [0,0,0,0][1,0,0,1] is_power_of_two = ((i & (i-1) == 0) and i != 0) if is_power_of_two: return int(np.log2(i)) else: return -3 def __eq__(self, other): if isinstance(other, int): self.encoder(other) eq_qbl = QuantumBool() cx(self[other], eq_qbl) return eq_qbl else: raise Exception( f"Comparison with type {type(other)} not implemented") __hash__ = QuantumVariable.__hash__ def is_even(self): is_even = QuantumBool() for i in range(self.size): if not i % 2: cx(self[i], is_even) return is_even def is_odd(self): is_odd = QuantumBool() for i in range(self.size): if i % 2: cx(self[i], is_odd) return is_odd def __lt__(self, other): if isinstance(other, int): less_than = QuantumBool() for i in range(self.size): if i < other: cx(self[i], less_than) return less_than else: raise Exception(f"Comparison for type {type(other)} not implemented") def fan_in(control, target): for qb in control: cx(control, target) """ This function realizes the operator U_x, which has the property U_x |x> = |psi_x> For more details on these objects, check the details of the paper (https://arxiv.org/abs/1509.02374)or the beginning of this file. The general idea to implement this operator are the following two steps: 1. Manipulatre h such that |h> -> 1/N(|h> + c*|h-1>) with suitable N,c \in R 2. Manipulate branch_qa controlled on h-1 to bring the new branches into into superposition. The value of the constant c depends on wether x is the root or a terminal node. For the root c = n**0.5*d_x**0.5 Otherwise c = d_x**0.5 Where d_x is the degree of the node. """ def psi_prep(x, even=True, min_height_assumption = 0): # Determine c c = x.degree**0.5 # The step |h> -> 1/N(|h> + c*|h-1>) will be performed by a ry gate phase = np.arctan(c)*2 root_phase = np.arctan((c*np.sqrt(x.max_depth)))*2 rev_branch_qa = x.branch_qa # N = x.max_depth+1 N = x.max_depth # To achieve the first step, we use a circuit, that performs a similar function # as a parametrized swap. That means: # |00> ==> |00> # |01> ==> sin(theta)*|01> + cos(theta)*|10> # |10> ==> cos(theta)*|10> + sin(theta)*|01> # |11> ==> |11> #This way we can "move" the 1 of the one hot encoding up and down. # After we moved the one, we apply an H-gate controlled on the target of the # moevement, to set up the super position in the branch_qa # Furthermore we also need to make sure that non-algorithmic states stay # invariant under the U_x (otherwise they will also get tagged in qstep_diffuser). # We achieve this by controlling the parameterized swap on the QuantumVariable # which would be set to super position by the controlled H-gate. # This QuantumVariable represents the branch information of the child states # of H_x = <{|y> | |x> -> |y>} U {|x>} >. # If it is in a non-zero state but the height variable indicates the parent # state, the state is invariant. if bool(N % 2) != even: c_iswap_reduced(root_phase, rev_branch_qa[N-1], x.h[N-1], x.h[N]) x.qs.append(ch_gate, [x.h[N-1], rev_branch_qa[N-1]]) for i in range(int(even), N-1, 2): if i + 1 < min_height_assumption: continue c_iswap_reduced(phase, rev_branch_qa[i], x.h[i], x.h[i+1]) x.qs.append(ch_gate, [x.h[i], rev_branch_qa[i]]) ch_gate = HGate().control() # This circuit is a slightly modified (and controlled) version of the XXPlusYY gate # https://qiskit.org/documentation/stubs/qiskit.circuit.library.XXPlusYYGate.html def c_iswap(phi, ctrl, target_1, target_0): h(target_1) cx(target_1, target_0) x(ctrl) ctrl.qs().append(RYGate(-phi/2).control(), [ctrl, target_0]) ctrl.qs().append(RYGate(-phi/2).control(), [ctrl, target_1]) x(ctrl) cx(target_1, target_0) h(target_1) # This circuit performs a similar function as the previous one but has a different # behavior on |11> and also requires less resources. # Since the |11> behavior is irrelevant we can also use this circuit. def c_iswap_reduced(phi, ctrl, target_0, target_1): phi = -phi/4 + np.pi/4 h(target_1) cx(target_1, target_0) x(ctrl) ry(phi, target_0) ry(phi, target_1) #Usually we would now execute two controlled H-gates #If there are multiple controls, we'd have to perform #the corresponding mcx gate twice (to have two multi controlled H gates) # ctrl.qs().append(ch_gate, [ctrl, target_0]) # ctrl.qs().append(ch_gate, [ctrl, target_1]) #Two prevent this situation we execute a circuit with the same semantics but #only a single mcx gate #-------------------------- #These one qubit gates make sure that the cx gates are acting as a controlled #H-Gate s([target_0, target_1]) h([target_0, target_1]) t([target_0, target_1]) if len(ctrl) == 1: cx(ctrl, target_0) cx(ctrl, target_1) else: cx(target_0, target_1) mcx(ctrl, target_0) cx(target_0, target_1) t_dg([target_0, target_1]) h([target_0, target_1]) s_dg([target_0, target_1]) #---------------------------- ry(-phi, target_0) ry(-phi, target_1) x(ctrl) cx(target_1, target_0) h(target_1) class Subtree(QuantumBacktrackingTree): def __init__(self, parent_tree, root_path): if len(root_path) > parent_tree.max_depth: raise Exception( "Tried to initialise subtree with root path longer than maximum depth") QuantumBacktrackingTree.__init__(self, parent_tree.max_depth, parent_tree.branch_qa[0], parent_tree.accept_function, parent_tree.reject_function, parent_tree.subspace_optimization ) self.max_depth = parent_tree.max_depth - len(root_path) self.root_path = root_path self.original_tree = parent_tree def init_node(self, path): self.h[:] = self.max_depth - len(path) path = self.root_path + path if len(path): self.branch_qa[-len(path):] = path[::-1] def init_phi(self, path): h_state = {} h_state[self.max_depth] = (self.max_depth)**0.5 for i in range(1, len(path)+1): h_state[self.max_depth - i] = (-1)**(i) self.h[:] = h_state rev_branch_qa = self.branch_qa[::-1] with self.h == self.max_depth: for k in range(len(self.root_path)): rev_branch_qa[k][:] = self.root_path[k] for i in range(1, len(path)+1): with self.h == self.max_depth - i: for j in range(i): rev_branch_qa[j].encode( path[j], permit_dirtyness=True) for k in range(len(self.root_path)): rev_branch_qa[k+i][:] = self.root_path[k] def subtree(self, path): return self.original_tree.subtree(path) def find_solution(tree, precision, cl_accept=None, traversed_nodes=None, measurement_kwargs={}): # The idea of this function is to use the quantum algorithm to check wether # a the subtree of a given node contains a solution and then recursively call # this function on that subtree. # If there is no classical accept function given, we create a copy of the original # tree and evaluate the quantum accept function on that node via the simulator if cl_accept is None: def cl_accept(path): if isinstance(tree, Subtree): copied_tree = tree.original_tree.copy() else: copied_tree = tree.copy() copied_tree.init_node(path) accept_qbl = copied_tree.accept() mes_res = accept_qbl.get_measurement() return mes_res == {True: 1} # The first step is to check wether the current root is a solution if isinstance(tree, Subtree): path = tree.root_path else: path = [] if cl_accept(path): return path elif tree.max_depth == 0: return None # This list keeps track of which nodes have already been checked for solutions if traversed_nodes is None: traversed_nodes = [] # Initialize the root node tree.init_node([]) # Perform quantum phase estimation qpe_res = tree.estimate_phase(precision) # Retrieve the measurement results mes_res = multi_measurement([qpe_res, tree.h, tree.branch_qa], **measurement_kwargs) # We will first check wether there is a solution # The s variable will contain the probability to measure # the qpe_res == 0 branch. s = 0 # This list will contain the possible branches new_branches = [] for k, v in mes_res.items(): # k[0] is the value of qpe_res if k[0] == 0: # If the measurement result is part of the qpe == 0 branch, add the # probability to s s += v new_branches.append(k) # If the probability is less then 0.25, there is no solution if s <= 0.25: return None # If the probability is between 0.25 and 0.375, the qpe needs more precision if s <= 0.375: raise Exception( "Executed find solution method of quantum backtracking algorithm with insufficient precision") # To find the next node to check we will use a heuristic. # After measurement of the 0 branch, the tree is collapsed to a state which # also contains the |phi> state. The phi state is a superposition of nodes # leading to the desired solution. # We assume that the outcome with the smallest tree.h value is the state # corresponding to |phi>. This proved to be the case in every situation we tested. # If this assumption for whichever reason is not correct, the solution will still # be found because of the recursive nature of this algorithm. # Sort for the value of tree.h new_branches.sort(key=lambda x: x[1]) for b in new_branches: # Get the path to the new node if isinstance(tree, Subtree): new_path=tree.original_tree.path_decoder(b[1], b[2]) else: new_path=tree.path_decoder(b[1], b[2]) # Continue if new_path was already explored if tuple(new_path) in traversed_nodes or tuple(new_path)==tuple(path): continue # Generate the subtree subtree=tree.subtree(new_path) # Recursive call solution=find_solution(subtree, precision, cl_accept, traversed_nodes, measurement_kwargs=measurement_kwargs) # Leave loop if solution was found if solution is not None: break else: traversed_nodes.append(tuple(new_path)) else: raise Exception( "Executed find solution method of quantum backtracking algorithm with insufficient precision") return solution class QBTNode: def __init__(self, tree, path, amplitude=None): self.h=tree.max_depth - len(path) self.path=path self.tree=tree self.amplitude=amplitude def __hash__(self): return hash(str(self.path)) def sv_specifier(self): amplitude_state_specifyer={ self.tree.h: self.tree.max_depth - len(self.path)} path=list(self.path) if isinstance(self.tree, Subtree): path=self.tree.root_path + path for k in range(len(self.tree.branch_qa)): if k < len(path): amplitude_state_specifyer[self.tree.branch_qa[-1-k]]=path[k] else: amplitude_state_specifyer[self.tree.branch_qa[-1-k]]=0 return amplitude_state_specifyer def __str__(self): return "QBTNode(path = " + str(self.path) + ", amplitude = " + str(self.amplitude) + ")" def __repr__(self): return str(self)