text: """Grover's algorithm and helper functions.
  
  Todo:
  
  * W gate construction (or perhaps -W gate based on Mermin's book)
  * Generalize the algorithm for an unknown function that returns 1 on multiple
    qubit states, not just one.
  * Implement _represent_ZGate in OracleGate
  """
  
  from __future__ import print_function, division
  
  from sympy import floor, pi, sqrt, sympify, eye
  from sympy.core.compatibility import range
  from sympy.core.numbers import NegativeOne
  from sympy.physics.quantum.qapply import qapply
  from sympy.physics.quantum.qexpr import QuantumError
  from sympy.physics.quantum.hilbert import ComplexSpace
  from sympy.physics.quantum.operator import UnitaryOperator
  from sympy.physics.quantum.gate import Gate
  from sympy.physics.quantum.qubit import IntQubit
  
  __all__ = [
      'OracleGate',
      'WGate',
      'superposition_basis',
      'grover_iteration',
      'apply_grover'
  ]
  
  
  def superposition_basis(nqubits):
      """Creates an equal superposition of the computational basis.
  
      Parameters
      ==========
  
      nqubits : int
          The number of qubits.
  
      Returns
      =======
  
      state : Qubit
          An equal superposition of the computational basis with nqubits.
  
      Examples
      ========
  
      Create an equal superposition of 2 qubits::
  
          >>> from sympy.physics.quantum.grover import superposition_basis
          >>> superposition_basis(2)
          |0>/2 + |1>/2 + |2>/2 + |3>/2
      """
  
      amp = 1/sqrt(2**nqubits)
      return sum([amp*IntQubit(n, nqubits) for n in range(2**nqubits)])
  
  
  class OracleGate(Gate):
      """A black box gate.
  
      The gate marks the desired qubits of an unknown function by flipping
      the sign of the qubits.  The unknown function returns true when it
      finds its desired qubits and false otherwise.
  
      Parameters
      ==========
  
      qubits : int
          Number of qubits.
  
      oracle : callable
          A callable function that returns a boolean on a computational basis.
  
      Examples
      ========
  
      Apply an Oracle gate that flips the sign of ``|2>`` on different qubits::
  
          >>> from sympy.physics.quantum.qubit import IntQubit
          >>> from sympy.physics.quantum.qapply import qapply
          >>> from sympy.physics.quantum.grover import OracleGate
          >>> f = lambda qubits: qubits == IntQubit(2)
          >>> v = OracleGate(2, f)
          >>> qapply(v*IntQubit(2))
          -|2>
          >>> qapply(v*IntQubit(3))
          |3>
      """
  
      gate_name = u'V'
      gate_name_latex = u'V'
  
      #-------------------------------------------------------------------------
      # Initialization/creation
      #-------------------------------------------------------------------------
  
      @classmethod
      def _eval_args(cls, args):
          # TODO: args[1] is not a subclass of Basic
          if len(args) != 2:
              raise QuantumError(
                  'Insufficient/excessive arguments to Oracle.  Please ' +
                  'supply the number of qubits and an unknown function.'
              )
          sub_args = (args[0],)
          sub_args = UnitaryOperator._eval_args(sub_args)
          if not sub_args[0].is_Integer:
              raise TypeError('Integer expected, got: %r' % sub_args[0])
  
          if not callable(args[1]):
              raise TypeError('Callable expected, got: %r' % args[1])
          return (sub_args[0], args[1])
  
      @classmethod
      def _eval_hilbert_space(cls, args):
          """This returns the smallest possible Hilbert space."""
          return ComplexSpace(2)**args[0]
  
      #-------------------------------------------------------------------------
      # Properties
      #-------------------------------------------------------------------------
  
      @property
      def search_function(self):
          """The unknown function that helps find the sought after qubits."""
          return self.label[1]
  
      @property
      def targets(self):
          """A tuple of target qubits."""
          return sympify(tuple(range(self.args[0])))
  
      #-------------------------------------------------------------------------
      # Apply
      #-------------------------------------------------------------------------
  
      def _apply_operator_Qubit(self, qubits, **options):
          """Apply this operator to a Qubit subclass.
  
          Parameters
          ==========
  
          qubits : Qubit
              The qubit subclass to apply this operator to.
  
          Returns
          =======
  
          state : Expr
              The resulting quantum state.
          """
          if qubits.nqubits != self.nqubits:
              raise QuantumError(
                  'OracleGate operates on %r qubits, got: %r'
                  % (self.nqubits, qubits.nqubits)
              )
          # If function returns 1 on qubits
              # return the negative of the qubits (flip the sign)
          if self.search_function(qubits):
              return -qubits
          else:
              return qubits
  
      #-------------------------------------------------------------------------
      # Represent
      #-------------------------------------------------------------------------
  
      def _represent_ZGate(self, basis, **options):
          """
          Represent the OracleGate in the computational basis.
          """
          nbasis = 2**self.nqubits  # compute it only once
          matrixOracle = eye(nbasis)
          # Flip the sign given the output of the oracle function
          for i in range(nbasis):
              if self.search_function(IntQubit(i, self.nqubits)):
                  matrixOracle[i, i] = NegativeOne()
          return matrixOracle
  
  
  class WGate(Gate):
      """General n qubit W Gate in Grover's algorithm.
  
      The gate performs the operation ``2|phi><phi| - 1`` on some qubits.
      ``|phi> = (tensor product of n Hadamards)*(|0> with n qubits)``
  
      Parameters
      ==========
  
      nqubits : int
          The number of qubits to operate on
  
      """
  
      gate_name = u'W'
      gate_name_latex = u'W'
  
      @classmethod
      def _eval_args(cls, args):
          if len(args) != 1:
              raise QuantumError(
                  'Insufficient/excessive arguments to W gate.  Please ' +
                  'supply the number of qubits to operate on.'
              )
          args = UnitaryOperator._eval_args(args)
          if not args[0].is_Integer:
              raise TypeError('Integer expected, got: %r' % args[0])
          return args
  
      #-------------------------------------------------------------------------
      # Properties
      #-------------------------------------------------------------------------
  
      @property
      def targets(self):
          return sympify(tuple(reversed(range(self.args[0]))))
  
      #-------------------------------------------------------------------------
      # Apply
      #-------------------------------------------------------------------------
  
      def _apply_operator_Qubit(self, qubits, **options):
          """
          qubits: a set of qubits (Qubit)
          Returns: quantum object (quantum expression - QExpr)
          """
          if qubits.nqubits != self.nqubits:
              raise QuantumError(
                  'WGate operates on %r qubits, got: %r'
                  % (self.nqubits, qubits.nqubits)
              )
  
          # See 'Quantum Computer Science' by David Mermin p.92 -> W|a> result
          # Return (2/(sqrt(2^n)))|phi> - |a> where |a> is the current basis
          # state and phi is the superposition of basis states (see function
          # create_computational_basis above)
          basis_states = superposition_basis(self.nqubits)
          change_to_basis = (2/sqrt(2**self.nqubits))*basis_states
          return change_to_basis - qubits
  
  
  def grover_iteration(qstate, oracle):
      """Applies one application of the Oracle and W Gate, WV.
  
      Parameters
      ==========
  
      qstate : Qubit
          A superposition of qubits.
      oracle : OracleGate
          The black box operator that flips the sign of the desired basis qubits.
  
      Returns
      =======
  
      Qubit : The qubits after applying the Oracle and W gate.
  
      Examples
      ========
  
      Perform one iteration of grover's algorithm to see a phase change::
  
          >>> from sympy.physics.quantum.qapply import qapply
          >>> from sympy.physics.quantum.qubit import IntQubit
          >>> from sympy.physics.quantum.grover import OracleGate
          >>> from sympy.physics.quantum.grover import superposition_basis
          >>> from sympy.physics.quantum.grover import grover_iteration
          >>> numqubits = 2
          >>> basis_states = superposition_basis(numqubits)
          >>> f = lambda qubits: qubits == IntQubit(2)
          >>> v = OracleGate(numqubits, f)
          >>> qapply(grover_iteration(basis_states, v))
          |2>
  
      """
      wgate = WGate(oracle.nqubits)
      return wgate*oracle*qstate
  
  
  def apply_grover(oracle, nqubits, iterations=None):
      """Applies grover's algorithm.
  
      Parameters
      ==========
  
      oracle : callable
          The unknown callable function that returns true when applied to the
          desired qubits and false otherwise.
  
      Returns
      =======
  
      state : Expr
          The resulting state after Grover's algorithm has been iterated.
  
      Examples
      ========
  
      Apply grover's algorithm to an even superposition of 2 qubits::
  
          >>> from sympy.physics.quantum.qapply import qapply
          >>> from sympy.physics.quantum.qubit import IntQubit
          >>> from sympy.physics.quantum.grover import apply_grover
          >>> f = lambda qubits: qubits == IntQubit(2)
          >>> qapply(apply_grover(f, 2))
          |2>
  
      """
      if nqubits <= 0:
          raise QuantumError(
              'Grover\'s algorithm needs nqubits > 0, received %r qubits'
              % nqubits
          )
      if iterations is None:
          iterations = floor(sqrt(2**nqubits)*(pi/4))
  
      v = OracleGate(nqubits, oracle)
      iterated = superposition_basis(nqubits)
      for iter in range(iterations):
          iterated = grover_iteration(iterated, v)
          iterated = qapply(iterated)
  
      return iterated
  