Common expressions for the theory of proveit.physics.quantum.QPE

In [1]:
import proveit
%common_expressions_notebook # Keep this at the top following 'import proveit'.
from proveit import defaults
from proveit import (Literal, Variable, ExprRange, ExprArray, VertExprArray,
                     ConditionalSet, Conditional)
from proveit import a, b, e, i, j, k, l, m, n, r, s, t, u, U, eps
from proveit.logic import (Set, Difference, InSet, Set, CartExp, 
                           Equals, NotEquals, SetOfAll)
from proveit.numbers import (
    zero, one, two, Abs, Add, Ceil, Complex, Exp, frac, greater, greater_eq,
    Interval, LessEq, Log, ModAbs, NaturalPos, Neg, Mult, Round, subtract, subtract)
from proveit.linear_algebra import MatrixExp
from proveit.statistics import Prob, ProbOfAll
from proveit.physics.quantum import Ket, NumKet, MEAS, I, Z, H, CONTROL, ket_plus
from proveit.physics.quantum.circuits import (
    Qcircuit, Input, Output, Gate, Measure, control_elem, multi_wire, 
    multi_input_entries, multi_output_entries, multi_gate_entries,
from proveit.physics.quantum.QFT import InverseFourierTransform
from proveit.physics.quantum.QPE import QPE, QPE1
from proveit.physics.quantum.QPE.phase_est_ops import ModAdd, SubIndexed
from proveit.numbers import Round
In [2]:
%begin common
Defining common sub-expressions for theory 'proveit.physics.quantum.QPE'
Subsequent end-of-cell assignments will define common sub-expressions
%end_common will finalize the definitions
In [3]:
# U: Unitary operator to apply quantum phase estimation.
_U = Literal('U')
In [4]:
# n: Number of qubits which U acts on.
_n = Literal('n')
In [5]:
# u: Eigenvector of U to apply the quantum phase estimation.
_ket_u = Literal('|u>', r'\lvert u \rangle')
In [6]:
# phase: Eigenvalue phase of u w.r.t. U.  U u = e^{i \varphi} u.
#        This \varphi is the phase that is the objective of phase estimation.
_phase = Literal('phase', latex_format=r'\varphi')
In [7]:
_phase_est = Literal('phase_est', latex_format=r'\tilde{\varphi}')
In [8]:
phase = Variable('phase', latex_format=r'\varphi')
In [9]:
phase_est = Variable('phase_est', latex_format=r'\tilde{\varphi}')
In [10]:
# t: Number of qubit registers for the quantum phase estimation.
#    We prove that this is the bits of precision of phase estimation.
_t = Literal('t')
In [11]:
_n = Literal('n')
In [12]:
_eps = Literal('eps', r'\epsilon')
In [13]:
# Psi: Outcome of register qubits following the quantum phase estimation circuit.
_Psi_ket = Literal('|Psi>', latex_format=r'\lvert \Psi \rangle')
In [14]:
# psi: indexed intermediate output registers inside the quantum phase estimation circuit.
_psi = Literal('psi', latex_format=r'\psi')
In [15]:
# SubIndexed puts in in a ket for display purposes.
_psi_t_ket = SubIndexed(_psi, t)
In [16]:
_psi__t_ket = SubIndexed(_psi, _t)
In [17]:
_psi_1 = SubIndexed(_psi, one)
In [18]:
_U_pow_two_pow_k = Exp(_U, Exp(two, k))
In [19]:
_s = Literal('s')
In [20]:
# Used to be
# m: Random variable for the measurement of Psi as an
#    integer from the register's binary representation.
# Now we are using it as the size of the |u> register.
# As of 10/25 back to using this for the measurement of Psi
# Now using s as the size of the |u> register
#_m = Literal('m')
In [21]:
# phase_m: Random variable for the phase result of the
#          quantum phase estimation phase_m = m / 2^t
#          (I wish the subscript appeared a bit lower)
#_phase_m = Literal('phase_m', latex_format=r'\varphi_m')
In [22]:
# b: The "best" outcome of measurement m, defined in Nielsen & Chuang
# such that b is the t-qubit estimate closest to, BUT LESS THAN, phase phi.
_b = Literal('b')
In [23]:
# b_f: The "best" outcome of measurement m, defined (in the axioms) as
# the best t-qubit under-estimate of the phase phi (i.e. the binary expansion
# of phi truncated to t-bits). The 'f' stands for 'floor'.
_b_floor = Literal('b_{f}', latex_format=r'b_{\textit{f}}')
In [24]:
# b_r: The "best" outcome of measurement m, now defined (in the axioms) as
# the t-qubit estimate closest to phase phi (i.e. the binary expansion of
# phi ROUNDED to t-bits). The 'r' stands for 'round'.
_b_round = Literal('b_{r}', latex_format=r'b_{\textit{r}}')
In [25]:
two_pow_t = Exp(two, t)
In [26]:
two_pow_s = Exp(two, s)
In [27]:
# 2^t
_two_pow_t = Exp(two, _t)
In [28]:
# 2^{t-1}
_two_pow__t_minus_one = Exp(two, subtract(_t, one))
In [29]:
# 2^{t+1}
_two_pow__t_plus_one = Exp(two, Add(_t, one))
In [30]:
_two_pow_t__minus_one = subtract(Exp(two, _t), one)
In [31]:
# amplitude of output register as indexed
_alpha = Literal('alpha', latex_format= r'\alpha')
In [32]:
# These are subscripted with letter l (ell), NOT numeral 1 (one)
_alpha_l = SubIndexed(_alpha, l)
In [33]:
_alpha_m = SubIndexed(_alpha, m)
In [34]:
from proveit.numbers import Mod
_alpha_l_mod_two_pow_t = SubIndexed(_alpha, Mod(l, _two_pow_t))
In [35]:
from proveit import m
from proveit.numbers import Mod
_alpha_m_mod_two_pow_t = SubIndexed(_alpha, Mod(m, _two_pow_t))
In [36]:
# These are subscripted with letter l (ell), NOT numeral 1 (one)
_alpha_bl = SubIndexed(_alpha, ModAdd(_b, l))
In [37]:
abs_a = Abs(a)
In [38]:
_abs_alpha_l = Abs(_alpha_l)
In [39]:
_alpha_l_sqrd = Exp(Abs(_alpha_l), two)
In [40]:
_rel_indexed_alpha = SubIndexed(_alpha, ModAdd(_b_floor, l))
In [41]:
_alpha_m_sqrd = Exp(Abs(_alpha_m), two)
In [42]:
# _delta: difference between the phase and the best t-qubit
# phase phase measurement _b/2^t (defined in axioms)
_delta = Literal('delta', latex_format=r'\delta')
In [43]:
_delta_b = SubIndexed(_delta, b)
In [44]:
# _delta__b_floor: difference between the phase and the best
# t-qubit phase underestimate measurement _b_round/2^t (defined in axioms)
# _delta_b_floor = Literal('delta_{b_f}', latex_format=r'\delta_{b_f}')
In [45]:
# _delta__b_floor: difference between the phase and the best
# t-qubit phase underestimate measurement _b_round/2^t (defined in axioms)
_delta_b_floor = SubIndexed(_delta, _b_floor)
In [46]:
# _delta_round: difference between the phase and the best (rounded)
# t-qubit phase phase measurement _b_round/2^t (defined in axioms)
_delta_b_round = SubIndexed(_delta, _b_round)
In [47]:
_diff_l_scaled_delta_floor = subtract(l, Mult(_two_pow_t, _delta_b_floor))
In [48]:
_full_domain = Interval(Add(Neg(Exp(two, subtract(_t, one))), one),
                     Exp(two, subtract(_t, one)))
In [49]:
_neg_domain = Interval(Add(Neg(_two_pow__t_minus_one), one), 
                     Neg(Add(e, one)))
In [50]:
_pos_domain = Interval(Add(e, one), 
In [51]:
_e_domain = Interval(one, subtract(_two_pow__t_minus_one, two))
In [52]:
_e_value = subtract(Exp(two, subtract(_t, _n)), one)
In [53]:
s_ket_domain = CartExp(Complex, Exp(two, s))
In [54]:
_t_wire = multi_wire(_t)
_s_wire = multi_wire(_s)
In [55]:
_qpe_multigate = [*multi_gate_entries(
    QPE(_U, _t), one, Add(_t, _s), (one, _t), (Add(_t, one), Add(_t, _s)))]
_QPE_U_t = Qcircuit(VertExprArray(
In [56]:
_qpe1_multigate = [*multi_gate_entries(
    QPE1(_U, _t), one, Add(_t, _s), (one, _t), (Add(_t, one), Add(_t, _s)))]
_QPE1_U_t = Qcircuit(VertExprArray(
In [57]:
_inv_FT = [*multi_gate_entries(InverseFourierTransform(_t), one, _t, (one, _t))]
_QPE_U_t_circuit = Qcircuit(VertExprArray(
    _qpe1_multigate, [*_inv_FT, _s_wire]))

These assumptions are needed for proper formatting of QPE1_U_t_circuit.

In [58]:
_qpe_inputs = [ExprRange(i, Input(ket_plus), one, _t),
               *multi_input_entries(_ket_u, Add(_t, one), Add(_t, _s), (one, _s))]
_u_outputs = [*multi_output_entries(_ket_u, Add(_t, one), Add(_t, _s), 
                                          (one, _s))]
_psi_t_circuit = Qcircuit(VertExprArray(
    _qpe_inputs, _qpe1_multigate,
    [*multi_output_entries(_psi_t_ket, one, _t, (one, _t)), 
In [59]:
_Psi_circuit = Qcircuit(VertExprArray(
    _qpe_inputs, _qpe_multigate,
    [*multi_output_entries(_Psi_ket, one, _t, (one, _t)), *_u_outputs]))
In [60]:
_phase_circuit = Qcircuit(VertExprArray(
    _qpe_inputs, _qpe_multigate,
    [ExprRange(i, Measure(Z), one, _t), _s_wire],
    [*multi_output_entries(NumKet(Mult(_two_pow_t, _phase), _t), 
                           one, _t, (one, _t)),
In [61]:
_phase_est_circuit_b_r = Qcircuit(VertExprArray(
    _qpe_inputs, _qpe_multigate,
    [ExprRange(i, Measure(Z), one, _t), _s_wire],
    [*multi_output_entries(NumKet(Mod(Round(Mult(_two_pow_t, _phase)), _two_pow_t), _t), 
                           one, _t, (one, _t)),
In [62]:
_phase_est_circuit = Qcircuit(VertExprArray(
    _qpe_inputs, _qpe_multigate,
    [ExprRange(i, Measure(Z), one, _t), _s_wire],
    [*multi_output_entries(NumKet(m, _t), 
                           one, _t, (one, _t)),
In [63]:
t_wire = multi_wire(t)
s_wire = multi_wire(s)
In [64]:
QPE1_U_t_circuit = Qcircuit(VertExprArray(
        [ExprRange(j, ConditionalSet(
                               control_elem(Add(t, one)),
                               Equals(Add(Neg(i), t), j)), 
                           Conditional(Gate(I), NotEquals(Add(Neg(i), t), j))),
                   one, t).with_case_simplification(), 
         *multi_gate_entries(MatrixExp(U, Exp(two, i)), 
                             Add(t, one), Add(t, s), (one, s))], 
              subtract(t, one), zero, order='decreasing').with_case_simplification()))
In [65]:
# This is incorrect (mod should be 2^t)
# _success_prob_e = Prob(LessEq(ModAbs(subtract(Mult(_two_pow_t, _phase_est), _b), one), 
#                               e), _phase_est)
In [66]:
# the _ideal_phase_cond captures the case where the phase _phi can be
# represented exactly with the t bits (or fewer) available in the first register
_ideal_phase_cond = InSet(Mult(_two_pow_t, _phase), 
                          Interval(zero, subtract(_two_pow_t, one)))
In [67]:
_m_domain = Interval(zero, _two_pow_t__minus_one)
In [68]:
_success_cond = LessEq(ModAbs(subtract(frac(m, _two_pow_t), _phase), one), 
                       Exp(two, Neg(_n)))
In [69]:
_Omega = Literal('Omega', r'\Omega')
In [70]:
_sample_space = SetOfAll(m, _phase_est_circuit, domain=_m_domain)
In [71]:
_success_prob_e = ProbOfAll(m, _phase_est_circuit,
                            condition=LessEq(ModAbs(subtract(m, _b_floor), _two_pow_t), e)).with_wrapping()
In [72]:
# Corrected mod and switched back to m instead of phi
_fail_prob_e = ProbOfAll(m, _phase_est_circuit,
                         condition=greater(ModAbs(subtract(m, _b_floor), _two_pow_t), e)).with_wrapping()
In [73]:
_Psi_register_meas = Qcircuit(VertExprArray(
    [*multi_input_entries(_Psi_ket, one, _t, (one, _t))], 
    [ExprRange(k, Measure(Z), one, _t)],
    [*multi_output_entries(NumKet(m, _t), one, _t, (one, _t))]))
In [74]:
# _success_prob_guarantee = greater_eq(_success_prob, subtract(one, _eps))
In [75]:
%end common
These common expressions may now be imported from the theory package: proveit.physics.quantum.QPE