|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"""Utils for the Maximum-Likelihood estimation used in ``AmplitudeEstimation``.""" |
|
|
|
import logging |
|
import numpy as np |
|
|
|
logger = logging.getLogger(__name__) |
|
|
|
|
|
|
|
|
|
def bisect_max(f, a, b, steps=50, minwidth=1e-12, retval=False): |
|
"""Find the maximum of the real-valued function f in the interval [a, b] using bisection. |
|
|
|
Args: |
|
f (callable): the function to find the maximum of |
|
a (float): the lower limit of the interval |
|
b (float): the upper limit of the interval |
|
steps (int): the maximum number of steps in the bisection |
|
minwidth (float): if the current interval is smaller than minwidth stop |
|
the search |
|
retval (bool): return value |
|
|
|
Returns: |
|
float: The maximum of f in [a,b] according to this algorithm. |
|
""" |
|
it = 0 |
|
m = (a + b) / 2 |
|
fm = 0 |
|
while it < steps and b - a > minwidth: |
|
l, r = (a + m) / 2, (m + b) / 2 |
|
fl, fm, fr = f(l), f(m), f(r) |
|
|
|
|
|
if fl > fm and fl > fr: |
|
b = m |
|
m = l |
|
|
|
elif fr > fm and fr > fl: |
|
a = m |
|
m = r |
|
|
|
else: |
|
a = l |
|
b = r |
|
|
|
it += 1 |
|
|
|
if it == steps: |
|
logger.warning("-- Warning, bisect_max didn't converge after %s steps", steps) |
|
|
|
if retval: |
|
return m, fm |
|
|
|
return m |
|
|
|
|
|
def _circ_dist(x, p): |
|
r"""Circumferential distance function. |
|
|
|
For two angles :math:`x` and :math:`p` on the unit circuit this function is defined as |
|
|
|
.. math:: |
|
|
|
d(x, p) = \min_{z \in [-1, 0, 1]} |z + p - x| |
|
|
|
Args: |
|
x (float): first angle |
|
p (float): second angle |
|
|
|
Returns: |
|
float: d(x, p) |
|
""" |
|
t = p - x |
|
|
|
|
|
z = np.array([-1, 0, 1]) |
|
|
|
if hasattr(t, "__len__"): |
|
d = np.empty_like(t) |
|
for idx, ti in enumerate(t): |
|
d[idx] = np.min(np.abs(z + ti)) |
|
return d |
|
|
|
return np.min(np.abs(z + t)) |
|
|
|
|
|
def _derivative_circ_dist(x, p): |
|
"""Derivative of circumferential distance function. |
|
|
|
Args: |
|
x (float): first angle |
|
p (float): second angle |
|
|
|
Returns: |
|
float: The derivative. |
|
""" |
|
|
|
t = p - x |
|
if t < -0.5 or (0 < t and t < 0.5): |
|
return -1 |
|
if t > 0.5 or (-0.5 < t and t < 0): |
|
return 1 |
|
return 0 |
|
|
|
|
|
def _amplitude_to_angle(a): |
|
r"""Transform from the amplitude :math:`a \in [0, 1]` to the generating angle. |
|
|
|
In QAE, the amplitude can be written from a generating angle :math:`\omega` as |
|
|
|
.. math: |
|
|
|
a = \sin^2(\pi \omega) |
|
|
|
This returns the :math:`\omega` for a given :math:`a`. |
|
|
|
Args: |
|
a (float): A value in :math:`[0,1]`. |
|
|
|
Returns: |
|
float: :math:`\sin^{-1}(\sqrt{a}) / \pi` |
|
""" |
|
return np.arcsin(np.sqrt(a)) / np.pi |
|
|
|
|
|
def _derivative_amplitude_to_angle(a): |
|
"""Compute the derivative of ``amplitude_to_angle``.""" |
|
return 1 / (2 * np.pi * np.sqrt((1 - a) * a)) |
|
|
|
|
|
def _alpha(x, p): |
|
"""Helper function for `pdf_a`, alpha = pi * d(omega(x), omega(p)). |
|
|
|
Here, omega(x) is `_amplitude_to_angle(x)`. |
|
""" |
|
omega = _amplitude_to_angle |
|
return np.pi * _circ_dist(omega(x), omega(p)) |
|
|
|
|
|
def _derivative_alpha(x, p): |
|
"""Compute the derivative of alpha.""" |
|
omega = _amplitude_to_angle |
|
d_omega = _derivative_amplitude_to_angle |
|
return np.pi * _derivative_circ_dist(omega(x), omega(p)) * d_omega(p) |
|
|
|
|
|
def _beta(x, p): |
|
"""Helper function for `pdf_a`, beta = pi * d(1 - omega(x), omega(p)).""" |
|
omega = _amplitude_to_angle |
|
return np.pi * _circ_dist(1 - omega(x), omega(p)) |
|
|
|
|
|
def _derivative_beta(x, p): |
|
"""Compute the derivative of beta.""" |
|
omega = _amplitude_to_angle |
|
d_omega = _derivative_amplitude_to_angle |
|
return np.pi * _derivative_circ_dist(1 - omega(x), omega(p)) * d_omega(p) |
|
|
|
|
|
def _pdf_a_single_angle(x, p, m, pi_delta): |
|
"""Helper function for `pdf_a`.""" |
|
M = 2**m |
|
|
|
d = pi_delta(x, p) |
|
res = np.sin(M * d) ** 2 / (M * np.sin(d)) ** 2 if d != 0 else 1 |
|
|
|
return res |
|
|
|
|
|
def pdf_a(x, p, m): |
|
""" |
|
Return the PDF of a, i.e. the probability of getting the estimate x |
|
(in [0, 1]) if p (in [0, 1]) is the true value, given that we use m qubits. |
|
|
|
Args: |
|
x (float): the grid point |
|
p (float): the true value |
|
m (float): the number of evaluation qubits |
|
|
|
Returns: |
|
float: PDF(x|p) |
|
""" |
|
|
|
scalar = False |
|
if not hasattr(x, "__len__"): |
|
scalar = True |
|
x = np.asarray([x]) |
|
|
|
|
|
|
|
|
|
pr = np.array( |
|
[ |
|
_pdf_a_single_angle(xi, p, m, _alpha) + _pdf_a_single_angle(xi, p, m, _beta) |
|
if (xi not in [0, 1]) |
|
else _pdf_a_single_angle(xi, p, m, _alpha) |
|
for xi in x |
|
] |
|
).flatten() |
|
|
|
|
|
return pr[0] if scalar else pr |
|
|
|
|
|
def derivative_log_pdf_a(x, p, m): |
|
""" |
|
Return the derivative of the logarithm of the PDF of a. |
|
|
|
Args: |
|
x (float): the grid point |
|
p (float): the true value |
|
m (float): the number of evaluation qubits |
|
|
|
Returns: |
|
float: d/dp log(PDF(x|p)) |
|
""" |
|
M = 2**m |
|
|
|
if x not in [0, 1]: |
|
num_p1 = 0 |
|
for A, dA, B, dB in zip( |
|
[_alpha, _beta], |
|
[_derivative_alpha, _derivative_beta], |
|
[_beta, _alpha], |
|
[_derivative_beta, _derivative_alpha], |
|
): |
|
num_p1 += 2 * M * np.sin(M * A(x, p)) * np.cos(M * A(x, p)) * dA(x, p) * np.sin( |
|
B(x, p) |
|
) ** 2 + 2 * np.sin(M * A(x, p)) ** 2 * np.sin(B(x, p)) * np.cos(B(x, p)) * dB(x, p) |
|
|
|
den_p1 = ( |
|
np.sin(M * _alpha(x, p)) ** 2 * np.sin(_beta(x, p)) ** 2 |
|
+ np.sin(M * _beta(x, p)) ** 2 * np.sin(_alpha(x, p)) ** 2 |
|
) |
|
|
|
num_p2 = 0 |
|
for A, dA, B in zip( |
|
[_alpha, _beta], [_derivative_alpha, _derivative_beta], [_beta, _alpha] |
|
): |
|
num_p2 += 2 * np.cos(A(x, p)) * dA(x, p) * np.sin(B(x, p)) |
|
|
|
den_p2 = np.sin(_alpha(x, p)) * np.sin(_beta(x, p)) |
|
|
|
return num_p1 / den_p1 - num_p2 / den_p2 |
|
|
|
return 2 * _derivative_alpha(x, p) * (M / np.tan(M * _alpha(x, p)) - 1 / np.tan(_alpha(x, p))) |
|
|