import logging
import math
from copy import deepcopy
from typing import Dict, List, Optional, Union, cast

import numpy as np
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import QuadraticForm, RYGate
from qiskit.primitives import BaseSampler
from qiskit.quantum_info import Operator
from qiskit_algorithms import AmplificationProblem
from qiskit_algorithms.amplitude_amplifiers.grover import Grover
from qiskit_algorithms.utils import algorithm_globals
from qiskit_aer import Aer
from qiskit import transpile, assemble
from qiskit_optimization.algorithms.optimization_algorithm import (
    OptimizationAlgorithm,
    OptimizationResult,
    OptimizationResultStatus,
    SolutionSample,
)

from qiskit_optimization.problems import QuadraticProgram, Variable
from qiskit.circuit.library import QFT
from qiskit_aer import AerSimulator
# ...[之前的代码]...
logger = logging.getLogger(__name__)
# 示例用法:
'''numbers = [55, 6, 83, 2, 94, 53, 28, 64, 75, 47, 93, 36, 23, 89, 84, 91, 76, 12, 40, 38, 86, 51, 25, 21, 72, 48, 31, 18,
           62, 66, 77, 13, 82, 61, 92, 81, 35, 71, 74, 98, 22, 96, 44, 43, 5, 100, 45, 30, 65, 85]'''


class GroverOptimizationResult:
    def __init__(self, keys, values, operation_counts, n_input_qubits, n_output_qubits, threshold, num_solutions):
        self.keys = keys
        self.values = values
        self.operation_counts = operation_counts
        self.n_input_qubits = n_input_qubits
        self.n_output_qubits = n_output_qubits
        self.threshold = threshold
        self.num_solutions = num_solutions
        self.status = OptimizationResultStatus.SUCCESS
        # 生成一个解决方案列表，每个解决方案都是一个由 0 和 1 组成的列表，表示键的二进制形式
        self.solutions = [[1 if i == key else 0 for i in range(num_solutions)] for key in keys]


class GroverOptimizer:
    def __init__(
            self,
            num_value_qubits: int,
            num_key_qubits: int,
            num_ancil_qubits: int = 1,
            num_iterations: int = 5,
            sampler: Optional[BaseSampler] = None,
    ) -> None:
        # ... [existing code] ...
        #if sampler is None:
         #   # Use Aer's qasm_simulator by default if no sampler is provided
          #  self._sampler = Aer.get_backend('qasm_simulator')
        #else:
         #   self._sampler = sampler
        # ... [existing code] ...

        self._num_ancil_qubits = num_ancil_qubits
        self._num_value_qubits = num_value_qubits
        self._num_key_qubits = num_key_qubits
        self._n_iterations = num_iterations
        #这行代码 self._circuit_results = {} # type: dict 在 GroverOptimizer 类的 init 方法中初始化了一个名为 _circuit_results 的实例变量，将其赋值为空字典。
        self._circuit_results = {}  # type: dict
        self._sampler = sampler
        self._MIN_PROBABILITY = 0.0000000000000001
    def get_compatibility_msg(self, problem: QuadraticProgram) -> str:
        return ""

    def _get_a_operator(self, numbers):
        # 初始化量子寄存器
        qr_key = QuantumRegister(self._num_key_qubits, 'key')
        qr_value = QuantumRegister(self._num_value_qubits, 'value')
        qr_ancil = QuantumRegister(1, 'ancil')
        # 初始化量子电路
        a_operator = QuantumCircuit(qr_key, qr_value, qr_ancil)

        # 将key和value寄存器的量子比特置于叠加态
        a_operator.h(qr_key)
        a_operator.h(qr_value)

        # 对辅助量子比特进行操作
        a_operator.rx(np.pi / 2, qr_ancil)
        a_operator.z(qr_ancil)
        a_operator.x(qr_ancil)

        # 对每个数字进行编码
        for idx, number in enumerate(numbers):
            applied_x = []
            # 对qr_key进行X门操作以对应正确的编号
            bin_index = format(idx, '0' + str(self._num_key_qubits) + 'b')[::-1]
            for i, bit in enumerate(bin_index):
                if bit == '0':
                    a_operator.x(qr_key[i])
                    applied_x.append(i)

            # 对每个qr_value的量子比特进行控制旋转门操作
            for i in range(self._num_value_qubits):
                # 计算旋转角度
                angle = 4 * np.pi * number / (2 ** self._num_value_qubits)
                # 创建控制旋转门RY
                ry_gate = RYGate(angle).control(len(qr_key) + 1)
                # 重复添加控制旋转门RY 2**i次
                for _ in range(2**i):
                    a_operator.append(ry_gate, qr_key[:] + [qr_value[i], qr_ancil[0]])

            # 重置已经添加过X门的qr_key量子比特
            for i in applied_x:
                a_operator.x(qr_key[i])

        # 对value寄存器应用逆量子傅里叶变换并对辅助量子比特进行操作
        #a_operator.append(QFT(self._num_value_qubits).inverse(), qr_value[:])
        a_operator.x(qr_ancil)
        a_operator.z(qr_ancil)
        a_operator.rx(-np.pi / 2, qr_ancil)

        return a_operator

    def _get_oracle(self, qr_key_value):
        # Build negative value oracle O.
        # 定义矩阵
        custom_matrix = np.array([[-1, 0], [0, 1]])
        # 创建一个 UnitaryGate
        custom_gate = Operator(custom_matrix)
        if qr_key_value is None:
            qr_key_value = QuantumRegister(self._num_key_qubits + self._num_value_qubits+self._num_ancil_qubits)
        oracle_bit = QuantumRegister(1, "oracle")
        oracle = QuantumCircuit(qr_key_value, oracle_bit)
        oracle.unitary(custom_gate, [self._num_key_qubits], label='Inverse Z gate')
        def is_good_state(measurement):
            """Check whether ``measurement`` is a good state or not."""
            value = measurement[
                self._num_key_qubits : self._num_key_qubits + self._num_value_qubits
            ]
            return value[0] == "0"  #下为高位
        return oracle, is_good_state #返回量子电路与是否为目标态


    def _apply_threshold_rotation(self, a_operator, threshold_complement, numbers):  # 需要添加逻辑，像QPE一样添加相位旋转
        # 对辅助量子比特进行操作
        qr_ancil=a_operator.qubits[self._num_key_qubits+self._num_value_qubits]
        a_operator.rx(np.pi / 2, qr_ancil)
        a_operator.z(qr_ancil)
        a_operator.x(qr_ancil)
        qr_key = a_operator.qubits[0:self._num_key_qubits]
        qr_value = a_operator.qubits[self._num_key_qubits:self._num_key_qubits+self._num_value_qubits]
        # 对每个数字进行编码
        for idx, number in enumerate(numbers):
            applied_x = []
            # 对qr_key进行X门操作以对应正确的编号
            bin_index = format(idx, '0' + str(self._num_key_qubits) + 'b')[::-1]
            for i, bit in enumerate(bin_index):
                if bit == '0':
                    a_operator.x(qr_key[i])
                    applied_x.append(i)

            # 对每个qr_value的量子比特进行控制旋转门操作
            for i in range(self._num_value_qubits):
                # 计算旋转角度
                angle = 4 * np.pi * threshold_complement / (2 ** self._num_value_qubits)
                # 创建控制旋转门RY
                ry_gate = RYGate(angle).control(len(qr_key) + 1)
                # 重复添加控制旋转门RY 2**i次
                for _ in range(2 ** i):
                    a_operator.append(ry_gate, qr_key[:] + [qr_value[i], qr_ancil])

            # 重置已经添加过X门的qr_key量子比特
            for i in applied_x:
                a_operator.x(qr_key[i])

        # 对value寄存器应用逆量子傅里叶变换并对辅助量子比特进行操作
        a_operator.append(QFT(self._num_value_qubits).inverse(), qr_value[:])
        a_operator.x(qr_ancil)
        a_operator.z(qr_ancil)
        a_operator.rx(-np.pi / 2, qr_ancil)

        return a_operator


    def solve(self, numbers: List[int], N: int) :#-> 'GroverOptimizer.GroverOptimizationResult': #这里调用的参数有问题，不应该有problem: QuadraticProgram
        #variable_names = ['x' + str(i) for i in range(len(numbers))]  # 生成变量名列表
       # self._num_key_qubits =10 #设置键的量子比特数为10，仅作测试使用
        n_largest_values_and_keys = sorted([(numbers[i], i) for i in range(N)], key=lambda x: x[0], reverse=True)
        n_largest_values = [item[0] for item in n_largest_values_and_keys]
        n_largest_keys = [item[1] for item in n_largest_values_and_keys]

        keys_measured = []
        for item in n_largest_values_and_keys:
            keys_measured.append(item[1])

        # 示例输出
        print("n_largest_values:", n_largest_values)
        print("n_largest_keys:", n_largest_keys)
        print("keys_measured:", keys_measured)

        # Variables for tracking the optimum.
        optimum_found = False #是否找到最佳值
        optimum_key = math.inf  #最佳的键
        optimum_value = math.inf #最佳的值
        threshold = 0   #阈值
        n_key = self._num_key_qubits #键量子比特数
        n_value = self._num_value_qubits #值量子比特数

        # Variables for tracking the solutions encountered.
        num_solutions = 2 ** n_key  #可能解的总数，也是数据的总量

        # Variables for result object.
        operation_count = {}  #字典，用于存储每次迭代的运算量
        iteration = 0 #迭代次数

        # Variables for stopping if we've hit the rotation max.
        rotations = 0  #旋转次数
        max_rotations = int(np.ceil(100 * np.pi / 4)) #旋转次数的最大值

        # Initialize oracle helper object.
        qr_key_value = QuantumRegister(self._num_key_qubits + self._num_value_qubits+self._num_ancil_qubits) #量子寄存器，长度为键值对的总和
        measurement = True
        oracle, is_good_state = self._get_oracle(qr_key_value)  #运行oracle，创建oracle与is_good_state
        # 创建原始的准备算子 A 并保存副本以供后续使用
        a_operator = self._get_a_operator(numbers)
        while not optimum_found:
            a_operator_copy = deepcopy(a_operator)  # 创建准备算子 A 的副本
            m = 1
            improvement_found = False #是否找到改进的解，注意与最佳解进行区分

            # Get oracle O and the state preparation operator A for the current threshold.
            if(threshold == 0):
                threshold_complement = 0
            else:
                threshold_complement = self._decimal_to_twos_complement(-threshold, self._num_value_qubits)
            # 将阈值的负值转换为补码十进制的表示形式
            a_operator_copy = self._apply_threshold_rotation(a_operator_copy, threshold_complement, numbers)
            # 需要注意后续使用的A算子都是a_operator_copy，这是a_operator的副本。代码旋转threshold的角度用于模拟减去常数值
            # 同时这里应该调用的是-threshold的补码的十进制

            #Iterate until we measure a negative.
            loops_with_no_improvement = 0
            while not improvement_found:
                # Determine the number of rotations.
                loops_with_no_improvement += 1 #未找到更优数之前循环的次数
                # Grover 算法中执行的旋转次数，决定了振幅放大的范围，只会在0~m-1中进行随机选取，也就是说当m=1时，是不会进行grover迭代的
                rotation_count = algorithm_globals.random.integers(0, m)
                rotations += rotation_count #总旋转次数
                # Apply Grover's Algorithm to find values below the threshold.
                # TODO: Utilize Grover's incremental feature - requires changes to Grover.
                amp_problem = AmplificationProblem(
                    oracle=oracle,
                    state_preparation=a_operator_copy,
                    is_good_state=is_good_state,
                ) #运行Grover算法的前提条件
                grover = Grover() #实例化
                circuit = grover.construct_circuit(
                    problem=amp_problem, power=rotation_count, measurement=measurement
                ) #构建grover电路

                # Get the next outcome.
                outcome = self._measure(circuit) #测量
                #print("circuit:", circuit)
                k = int(outcome[2+n_value:n_key+2+n_value], 2) #从测量结果中提取键部分，将其从二进制字符串转化为整数。
                print("outcome:", outcome)
                v = outcome[2: 2 + n_value] #从测量结果中提取值部分，作为二进制字符串。
                # print("n_key+n_value=", n_key+n_value)
                # 在 solve 方法中
                int_v = GroverOptimizer._bin_to_int(v, n_value) + threshold  # 正确的静态方法调用
                # int_v=int(outcome[n_key: n_key + n_value], 2)+threshold
                # int_v = int(v, 2) + threshold
                # 方式
                logger.info("Outcome: %s", outcome)
                logger.info("Value Q(x): %s", int_v)  # 将最新的最佳键和最佳值记录在日志中。
                # If the value is an improvement, we update the iteration parameters (e.g. oracle).
                # 上述为Grover迭代，下述为条件判断
                # ... [之前的代码] ...

                # 检查新值是否足够小以被考虑为最小的 N 个值之一
                # 如果新值大于 n_largest_values 中的最小值（列表的最后一个元素），更新列表
                if int_v in numbers and (len(n_largest_values) < N or int_v > n_largest_values[-1]):
                    if k not in keys_measured:
                        # 找到并移除 n_largest_values 中的最小值，并添加新值
                        if len(n_largest_values) == N:
                            print("delete_value: ", n_largest_values.pop(-1))
                            print("delete_key: ", n_largest_keys.pop(-1))
                            n_largest_values.pop(-1)  # 移除最小值（列表的最后一个元素）
                            n_largest_keys.pop(-1)
                        print("add_value:", int_v)
                        print("add_key:", k)
                        n_largest_values.append(int_v)
                        n_largest_keys.append(k)
                        keys_measured.append(k)
                        print(keys_measured)

                        # 保持 n_largest_values 和 n_largest_keys 同步降序排列
                        sorted_pairs = sorted(zip(n_largest_values, n_largest_keys), reverse=True)
                        n_largest_values, n_largest_keys = zip(*sorted_pairs)
                        n_largest_values = list(n_largest_values)
                        n_largest_keys = list(n_largest_keys)

                        print("n_largest_values", n_largest_values)
                        print("n_largest_keys", n_largest_keys)

                        # 更新阈值为 n_largest_values 中的最小值
                        threshold = n_largest_values[-1]
                        improvement_found = True

                else:
                    print("else:")
                # Using Durr and Hoyer method, increase m.
                    m = int(np.ceil(min(m * 8 / 7, 2 ** (n_key / 2)))) #先取小，再向上取整
                    logger.info("No Improvement. M: %s", m) #将没有改进的信息记录在日志中。

                    # Check if we've already seen this value.
                    if k not in keys_measured: #如果键没有在已测量的列表中，就将其填入
                        keys_measured.append(k)
                    print(keys_measured)
                    # 检查是否达到了停止条件，如果是，则标记找到最佳解和改进的解
                    if (
                           loops_with_no_improvement >= self._n_iterations
                            or len(keys_measured) == len(numbers)  #将len(keys_measured) == num_solutions进行修改，因为这两项不一定是相等的
                            or rotations >= max_rotations
                    ):
                        improvement_found = True
                        optimum_found = True
                # 恢复电路
                #a_operator_copy=self._apply_threshold_rotation(a_operator_copy, threshold_relive)
                # Track the operation count.
                operations = circuit.count_ops()#计算电路中的操作计数。
                operation_count[iteration] = operations#记录每次迭代中的操作计数。
                iteration += 1
                logger.info("Operation Count: %s\n", operations)    #记录操作计数。
        # 在 solve 方法的末尾
        result = GroverOptimizationResult(
            keys=n_largest_keys,
            values=n_largest_values,
            operation_counts=operation_count,
            n_input_qubits=n_key,
            n_output_qubits=n_value,
            threshold=threshold,
            num_solutions=len(numbers)
        )
        return result

    def _measure(self, circuit: QuantumCircuit) -> str:
        """Get probabilities from the given backend, and picks a random outcome."""
        probs = self._get_prob_dist(circuit)
        logger.info("Frequencies: %s", probs)
        # Pick a random outcome.
        # 归一化概率，使总和为1
        total_prob = sum(probs.values())
        normalized_probs = [p / total_prob for p in probs.values()]
        return algorithm_globals.random.choice(list(probs.keys()), 1, p=normalized_probs)[0]




    def _get_prob_dist(self, qc: QuantumCircuit) -> Dict[str, float]:
        """使用 transpile 准备并执行量子电路，获取概率分布。"""
        #simulator = AerSimulator(method='statevector_gpu')  # 使用GPU加速，但没有显卡
        simulator = AerSimulator()
        # 使用 transpile 函数来准备电路，优化以适应特定的模拟器后端
        transpiled_circuit = transpile(qc, simulator)

        # 使用后端的 run 方法执行量子电路，并等待结果
        job = simulator.run(transpiled_circuit, shots=1024)
        result = job.result()
        counts = result.get_counts(qc)

        # 计算概率分布
        total_shots = sum(counts.values())
        prob_dist = {state: count / total_shots for state, count in counts.items() if
                     count / total_shots >= self._MIN_PROBABILITY}

        return prob_dist
    @staticmethod
    def _bin_to_int(v: str, num_value_bits: int) -> int:
        """将一个使用二进制补码形式表示的字符串转换为一个整数。"""
        if v.startswith("1"):
            int_v = int(v, 2) - 2**num_value_bits
        else:
            int_v = int(v, 2)

        return int_v

    def _decimal_to_twos_complement(self,negative_decimal, num_bits):
        # Calculate the two's complement binary representation
        # for the given negative decimal number and bit width
        mask = 2 ** num_bits - 1
        twos_complement = (abs(negative_decimal) ^ mask) + 1
        return twos_complement

阅读上述代码，计算其算法对应的时间复杂度，并将其与经典算法进行对比，包括最好时间复杂度、最坏时间复杂度