'''simple docstring'''

import mpmath  # for roots of unity
import numpy as np



class       UpperCAmelCase  :





       '''simple docstring'''



       def __init__(						self     ,       __lowerCAmelCase=None     ,       __lowerCAmelCase=None			)  ->  Union[str, Any]:
        # Input as list
        lowercase__    :   Tuple						= list(poly_a or [0]			)[:]
        lowercase__    :   int						= list(poly_b or [0]			)[:]

        # Remove leading zero coefficients
        while self.polyA[-1] == 0:
         self.polyA.pop()
        lowercase__    :   Any						= len(self.polyA			)

        while self.polyB[-1] == 0:
         self.polyB.pop()
        lowercase__    :   List[str]						= len(self.polyB			)

        # Add 0 to make lengths equal a power of 2
        lowercase__    :   str						= int(
            2 ** np.ceil(np.loga(len(self.polyA			) + len(self.polyB			) - 1			)			)			)

        while len(self.polyA			) < self.c_max_length:
         self.polyA.append(0			)
        while len(self.polyB			) < self.c_max_length:
         self.polyB.append(0			)
        # A complex root used for the fourier transform
        lowercase__    :   List[Any]						= complex(mpmath.root(x=1     ,       n=self.c_max_length     ,       k=1			)			)

        # The product
        lowercase__    :   List[str]						= self.__multiply()

       def _lowerCAmelCase(						self     ,       __lowerCAmelCase			)  ->  Any:
        lowercase__    :   List[str]						= [[x] for x in self.polyA] if which == '''A''' else [[x] for x in self.polyB]
        # Corner case
        if len(__lowerCAmelCase			) <= 1:
         return dft[0]
        #
        lowercase__    :   Optional[int]						= self.c_max_length // 2
        while next_ncol > 0:
         lowercase__    :   int						= [[] for i in range(__lowerCAmelCase			)]
         lowercase__    :   Any						= self.root**next_ncol

         # First half of next step
         lowercase__    :   List[str]						= 1
         for j in range(self.c_max_length // (next_ncol * 2)			):
          for i in range(__lowerCAmelCase			):
           new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]			)
          current_root *= root
         # Second half of next step
         lowercase__    :   Dict						= 1
         for j in range(self.c_max_length // (next_ncol * 2)			):
          for i in range(__lowerCAmelCase			):
           new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]			)
          current_root *= root
         # Update
         lowercase__    :   Dict						= new_dft
         lowercase__    :   str						= next_ncol // 2
        return dft[0]

       def _lowerCAmelCase(						self			)  ->  int:
        lowercase__    :   List[Any]						= self.__dft('''A'''			)
        lowercase__    :   Union[str, Any]						= self.__dft('''B'''			)
        lowercase__    :   Optional[Any]						= [[dft_a[i] * dft_b[i] for i in range(self.c_max_length			)]]
        del dft_a
        del dft_b

        # Corner Case
        if len(inverce_c[0]			) <= 1:
         return inverce_c[0]
        # Inverse DFT
        lowercase__    :   int						= 2
        while next_ncol <= self.c_max_length:
         lowercase__    :   str						= [[] for i in range(__lowerCAmelCase			)]
         lowercase__    :   str						= self.root ** (next_ncol // 2)
         lowercase__    :   int						= 1
         # First half of next step
         for j in range(self.c_max_length // next_ncol			):
          for i in range(next_ncol // 2			):
           # Even positions
           new_inverse_c[i].append(
               (
                   inverce_c[i][j]
                   + inverce_c[i][j + self.c_max_length // next_ncol]
               )
               / 2			)
           # Odd positions
           new_inverse_c[i + next_ncol // 2].append(
               (
                   inverce_c[i][j]
                   - inverce_c[i][j + self.c_max_length // next_ncol]
               )
               / (2 * current_root)			)
          current_root *= root
         # Update
         lowercase__    :   List[str]						= new_inverse_c
         next_ncol *= 2
        # Unpack
        lowercase__    :   Dict						= [round(x[0].real     ,       8			) + round(x[0].imag     ,       8			) * 1j for x in inverce_c]

        # Remove leading 0's
        while inverce_c[-1] == 0:
         inverce_c.pop()
        return inverce_c


       def __str__(						self			)  ->  Union[str, Any]:
        lowercase__    :   List[str]						= '''A = ''' + ''' + '''.join(
            F"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]			)			)
        lowercase__    :   str						= '''B = ''' + ''' + '''.join(
            F"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]			)			)
        lowercase__    :   Union[str, Any]						= '''A*B = ''' + ''' + '''.join(
            F"""{coef}*x^{i}""" for coef, i in enumerate(self.product			)			)

        return F"""{a}\n{b}\n{c}"""


# Unit tests
if __name__ == "__main__":
  import doctest

  doctest.testmod()


'''simple docstring'''

import qiskit
def       __UpperCamelCase	(       UpperCAmelCase		,					UpperCAmelCase					):
 lowercase__    :   Dict						= qiskit.Aer.get_backend('''aer_simulator'''					)

 # Create a Quantum Circuit acting on the q register
 lowercase__    :   Any						= qiskit.QuantumCircuit(UpperCAmelCase		,					UpperCAmelCase					)

 # Map the quantum measurement to the classical bits
 circuit.measure([0]		,					[0]					)

 # Execute the circuit on the simulator
 lowercase__    :   Any						= qiskit.execute(UpperCAmelCase		,					UpperCAmelCase		,					shots=1000					)

 # Return the histogram data of the results of the experiment.
 return job.result().get_counts(UpperCAmelCase					)


if __name__ == "__main__":
  print(F'Total count for various states are: {single_qubit_measure(1, 1)}')

