Cirq-FT: KOs Mean Estimation Algorithm Improvements

[tanujkhattar]

cirq-ft/cirq_ft/algos/mean_estimation/ implements the mean estimation algorithm described in Mean estimation when you have the source code; or, quantum Monte Carlo methods. Another good resource for learning the algorithm is https://youtu.be/W3aLlgrINxE

This issue tracks feature requests for improving the implementation of the algorithm in cirq-ft.

• ComplexPhaseOracle currently assumes that the random variable $y_{l}$ only takes integer
  values. This constraint can be removed by using a standardized floating point to
  binary encoding, like IEEE 754, to encode arbitrary floats in the binary target
  register and use them to compute the more accurate $-2\arctan({y_{l}})$ for any arbitrary
  $y_{l}$.

• cirq_ft.t_complexity(mean_gate) would currently because cirq.t_complexity(cirq.CZ ** exp) fails for arbitrary floating point powers exp. This should be fixed, probably as part of Improve coverage of _decompose_into_clifford_with_qubits_ and has_stabilizer_effect protocols Cirq#5906

• Right now, we have the tools to implement the "mean estimation unitary" which we can then do phase estimation / hadamard test on solve the problem stated in Theorem 1.3. But to solve the original mean estimation problem, we also need to implement the classical reductions in Section-4 of the paper. This sub-task is to track the implementation of reductions in Section 4 of the paper.

[skushnir123]

I can take this issue

[mpharrigan]

Is this still relevant?