Source code for qrisp.algorithms.grover.grover_tools

"""
\********************************************************************************
* 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
********************************************************************************/
"""


import numpy as np
from qrisp import QuantumArray, QuantumVariable, gate_wrap, gphase, h, mcp, mcz, x, merge, recursive_qs_search, IterationEnvironment, conjugate, invert


# Applies the grover diffuser onto the (list of) quantum variable input_object
def diffuser(input_object, phase=np.pi, state_function=None):
    """
    Applies the Grover diffuser onto (multiple) QuantumVariables.

    Parameters
    ----------
    input_object : QuantumVariable or list[QuantumVariable]
        The (list of) QuantumVariables to apply the Grover diffuser on.
    state_function : function
        A Python function preparing the initial state. The default is None.

    Examples
    --------

    We apply the Grover diffuser onto several QuantumChars:

    >>> from qrisp import QuantumChar
    >>> from qrisp.grover import diffuser
    >>> q_ch_list = [QuantumChar(), QuantumChar(), QuantumChar()]
    >>> diffuser(q_ch_list)
    >>> print(q_ch_list[0].qs)
    
    ::

                  ┌────────────┐
        q_ch_0.0: ┤0           ├
                  │            │
        q_ch_0.1: ┤1           ├
                  │            │
        q_ch_0.2: ┤2           ├
                  │            │
        q_ch_0.3: ┤3           ├
                  │            │
        q_ch_0.4: ┤4           ├
                  │            │
        q_ch_1.0: ┤5           ├
                  │            │
        q_ch_1.1: ┤6           ├
                  │            │
        q_ch_1.2: ┤7  diffuser ├
                  │            │
        q_ch_1.3: ┤8           ├
                  │            │
        q_ch_1.4: ┤9           ├
                  │            │
        q_ch_2.0: ┤10          ├
                  │            │
        q_ch_2.1: ┤11          ├
                  │            │
        q_ch_2.2: ┤12          ├
                  │            │
        q_ch_2.3: ┤13          ├
                  │            │
        q_ch_2.4: ┤14          ├
                  └────────────┘
                  
    """
    init_state = True if state_function is not None else False
    if init_state:
        def inv_state_function(args):
            with invert():
                state_function(*args)

    if isinstance(input_object, QuantumArray):
        input_object = [qv for qv in input_object.flatten()]

    if isinstance(input_object, list):
        if init_state:
            with conjugate(inv_state_function)(input_object):
                tag_state(
                    {qv: "0" * qv.size for qv in input_object}, binary_values=True, phase=phase
                )    
        else:
            [h(qv) for qv in input_object]
            tag_state(
                {qv: "0" * qv.size for qv in input_object}, binary_values=True, phase=phase
            )
            [h(qv) for qv in input_object]
        gphase(np.pi, input_object[0][0])
    else:
        if init_state:
            with conjugate(inv_state_function)(input_object):
                tag_state(
                    {input_object: input_object.size * "0"}, binary_values=True, phase=phase
                )
        else:
            h(input_object)
            tag_state(
                {input_object: input_object.size * "0"}, binary_values=True, phase=phase
            )
            h(input_object)
        gphase(np.pi, input_object[0])

    return input_object


def tag_state(tag_specificator, binary_values=False, phase=np.pi):
    """
    Applies a phase tag to (multiple) QuantumVariables. The tagged state is specified in
    the dictionary ``tag_specificator``. This dictionary should contain the
    QuantumVariables as keys and the labels of the states which should be tagged as
    values.


    Parameters
    ----------
    tag_specificator : dict
        A dictionary specifying which state should be tagged.
    binary_values : bool, optional
        If set to True, the values in the tag_specificator dict have to be bitstrings
        instead of labels. The default is False.
    phase : float or sympy.Symbol, optional
        Specify the phase shift the tag should perform. The default is pi, i.e. a
        multi-controlled Z gate.


    Examples
    --------

    We construct an oracle that tags the states -3 and 2 on two QuantumFloats ::

        from qrisp.grover import tag_state

        def test_oracle(qf_list):

            tag_dic = {qf_list[0] : -3, qf_list[1] : 2}

            tag_state(tag_dic)

    """

    qv_list = list(tag_specificator.keys())

    states = [tag_specificator[qv] for qv in qv_list]

    if not len(states):
        states = ["1" * qv.size for qv in qv_list]

    bit_string = ""
    from qrisp.misc import bin_rep

    for i in range(len(qv_list)):
        if binary_values:
            bit_string += states[i][::-1]
        else:
            bit_string += bin_rep(qv_list[i].encoder(states[i]), qv_list[i].size)[::-1]

    qubit_list = sum([list(qv.reg) for qv in qv_list], [])
    state = bit_string

    if state[-1] == "0":
        x(qubit_list[-1])

    # The control state is the state we are looking for without the base qubit
    ctrl_state = state[:-1]
    if phase == np.pi:
        mcz(qubit_list, ctrl_state=ctrl_state + "1")
    else:
        mcp(phase, qubit_list, ctrl_state=ctrl_state + "1")

    # Apply the final x gate
    if state[-1] == "0":
        x(qubit_list[-1])


[docs] def grovers_alg( qv_list, oracle_function, kwargs={}, iterations=0, winner_state_amount=None, exact=False, ): r""" Applies Grover's algorithm to a given oracle (in the form of a Python function). Parameters ---------- qv_list : QuantumVariable or list[QuantumVariable] A (list of) QuantumVariables on which to execute Grover's algorithm. oracle_function : function A Python function tagging the winner states. kwargs : dict, optional A dictionary containing keyword arguments for the oracle. The default is {}. iterations : int, optional The amount of Grover iterations to perfrom. winner_state_amount : int, optional If not given the amount of iterations, the established formula will be used based on the amount of winner states. The default is 1. exact : bool, optional If set to True, the `exact version <https://arxiv.org/pdf/quant-ph/0106071.pdf>` of Grover's algorithm will be evaluated. For this, the correct ``winner_state_amount`` has to be supplied and the oracle has to support the keyword argument ``phase`` which specifies how much the winner states are phaseshifted (in standard Grover this would be $\pi$). Raises ------ Exception Applied oracle introducing new QuantumVariables without uncomputing/deleting Examples -------- We construct an oracle that tags the states -3 and 2 on two QuantumFloats and apply Grover's algorithm to it. :: from qrisp import QuantumFloat #Create list of QuantumFloats qf_list = [QuantumFloat(2, signed = True), QuantumFloat(2, signed = True)] from qrisp.grover import tag_state, grovers_alg def test_oracle(qf_list): tag_dic = {qf_list[0] : -3, qf_list[1] : 2} tag_state(tag_dic) grovers_alg(qf_list, test_oracle) >>> from qrisp.misc import multi_measurement >>> print(multi_measurement(qf_list)) {(-3, 2): 0.9966, (0, 0): 0.0001, (0, 1): 0.0001, (0, 2): 0.0001, (0, 3): 0.0001, (0, -4): 0.0001, (0, -3): 0.0001, (0, -2): 0.0001, (0, -1): 0.0001, (1, 0): 0.0001, (1, 1): 0.0001, (1, 2): 0.0001, (1, 3): 0.0001, (1, -4): 0.0001, (1, -3): 0.0001, (1, -2): 0.0001, (1, -1): 0.0001, (2, 0): 0.0001, (2, 1): 0.0001, (2, 2): 0.0001, (2, 3): 0.0001, (2, -4): 0.0001, (2, -3): 0.0001, (2, -2): 0.0001, (2, -1): 0.0001, (3, 0): 0.0001, (3, 1): 0.0001, (3, 2): 0.0001, (3, 3): 0.0001, (3, -4): 0.0001, (3, -3): 0.0001, (3, -2): 0.0001, (3, -1): 0.0001, (-4, 0): 0.0001, (-4, 1): 0.0001, (-4, 2): 0.0001, (-4, 3): 0.0001, (-4, -4): 0.0001, (-4, -3): 0.0001, (-4, -2): 0.0001, (-4, -1): 0.0001, (-3, 0): 0.0001, (-3, 1): 0.0001, (-3, 3): 0.0001, (-3, -4): 0.0001, (-3, -3): 0.0001, (-3, -2): 0.0001, (-3, -1): 0.0001, (-2, 0): 0.0001, (-2, 1): 0.0001, (-2, 2): 0.0001, (-2, 3): 0.0001, (-2, -4): 0.0001, (-2, -3): 0.0001, (-2, -2): 0.0001, (-2, -1): 0.0001, (-1, 0): 0.0001, (-1, 1): 0.0001, (-1, 2): 0.0001, (-1, 3): 0.0001, (-1, -4): 0.0001, (-1, -3): 0.0001, (-1, -2): 0.0001, (-1, -1): 0.0001} **Exact Grovers Algorithm** In the next example, we will showcase the ``exact`` functionality. For this we create an oracle, which tags all the states of a QuantumVariable, that contain 3 ones and 2 zeros. To count the amount of ones we use quantum phase estimation on the operator .. math:: U = \text{exp}\left(\frac{i 2 \pi}{2^k} \sum_{i = 0}^{n-1} ( 1 - \sigma_{z}^i )\right) :: from qrisp import QPE, p, QuantumVariable, lifted from qrisp.grover import grovers_alg, tag_state import numpy as np def U(qv, prec = None, iter = 1): for i in range(qv.size): p(iter*2*np.pi/2**prec, qv[i]) @lifted def count_ones(qv): prec = int(np.ceil(np.log2(qv.size+1))) res = QPE(qv, U, precision = prec, iter_spec = True, kwargs = {"prec" : prec}) return res<<prec Quick test: >>> qv = QuantumVariable(5) >>> qv[:] = {"11000" : 1, "11010" : 1, "11110" : 1} >>> count_qf = count_ones(qv) >>> count_qf.qs.statevector() sqrt(3)*(|11000>*|2> + |11010>*|3> + |11110>*|4>)/3 We now define the oracle :: def counting_oracle(qv, phase = np.pi, k = 1): count_qf = count_ones(qv) tag_state({count_qf : k}, phase = phase) count_qf.uncompute() And evaluate Grover's algorithm :: n = 5 k = 3 qv = QuantumVariable(n) import math grovers_alg(qv, counting_oracle, exact = True, winner_state_amount = math.comb(n,k), kwargs = {"k" : k}) # noqa >>> print(qv) {'11100': 0.1, '11010': 0.1, '10110': 0.1, '01110': 0.1, '11001': 0.1, '10101': 0.1, '01101': 0.1, '10011': 0.1, '01011': 0.1, '00111': 0.1} We see that contrary to regular Grover's algorithm, the states which have not been tagged by the oracle have 0 percent measurement probability. """ if exact and winner_state_amount is None: raise Exception( "Tried to call exact Grover's algorithm without specifying " "winner_state_amount" ) elif winner_state_amount is None: winner_state_amount = 1 if isinstance(qv_list, list): N = 2 ** sum([qv.size for qv in qv_list]) elif isinstance(qv_list, QuantumArray): N = 2 ** sum([qv.size for qv in qv_list.flatten()]) elif isinstance(qv_list, QuantumVariable): N = 2**qv_list.size if exact: # Implementation for phase calculation for exact grovers alg as in # https://arxiv.org/pdf/quant-ph/0106071.pdf iterations = 1 tmp = ( np.sin(np.pi / (4 * (iterations - 1) + 6)) * (N / winner_state_amount) ** 0.5 ) while tmp > 1: iterations += 1 tmp = ( np.sin(np.pi / (4 * (iterations - 1) + 6)) * (N / winner_state_amount) ** 0.5 ) phi = 2 * np.arcsin( np.sin(np.pi / (4 * (iterations - 1) + 6)) * (N / winner_state_amount) ** 0.5 ) else: if iterations == 0: iterations = np.pi / 4 * np.sqrt(N / winner_state_amount) iterations = int(np.round(iterations)) for qv in qv_list: h(qv) merge(qv_list) qs = recursive_qs_search(qv_list)[0] qv_amount = len(qs.qv_list) with IterationEnvironment(qs, iterations, precompile = False): # for i in range(iterations): if exact: oracle_function(qv_list, phase=phi, **kwargs) diffuser(qv_list, phase=phi) else: oracle_function(qv_list, **kwargs) diffuser(qv_list) if qv_amount != len(qs.qv_list): raise Exception("Applied oracle introducing new QuantumVariables without uncomputing/deleting")
# Workaround to keep the docstring but still gatewrap temp = diffuser.__doc__ diffuser = gate_wrap(permeability=[], is_qfree=False)(diffuser) diffuser.__doc__ = temp temp = tag_state.__doc__ tag_state = gate_wrap(permeability="args", is_qfree=True)(tag_state) tag_state.__doc__ = temp