Proof of proveit.physics.quantum.QPE.qpe_exact theorem

import proveit
theory = proveit.Theory() # the theorem's theory

from proveit import defaults, Lambda
from proveit import a, b, m, t
from proveit.logic import And, Iff
from proveit.numbers import zero, two, Less, LessEq, greater, Exp
from proveit.physics.quantum.algebra import Ket
from proveit.physics.quantum.QPE import ModAdd
from proveit.physics.quantum.QPE import (
    _phase, _alpha_ideal_case, _outcome_prob, _phase_in_interval, 
    _t, _t_in_natural_pos, _two_pow_t_is_nat_pos)

%proving qpe_exact

With these allowed/disallowed theorem/theory presumptions (e.g., to avoid circular dependencies), we begin our proof of
qpe_exact:
(see dependencies)

First, we'll prove the instance expression in terms of the local QPE literals

_outcome_prob

 ⊢  

_alpha_ideal_case

 ⊢  

defaults.assumptions = [_alpha_ideal_case.antecedent]

defaults.assumptions:

alpha_eq1 = _alpha_ideal_case.derive_consequent()

alpha_eq1:  ⊢  

_m = alpha_eq1.lhs.index

_m:

prob_eq_1 = _outcome_prob.instantiate({m:_m}, replacements=[alpha_eq1])

prob_eq_1:  ⊢  

qpe_exact_with_extra_cond = prob_eq_1.generalize(
            qpe_exact.instance_param_lists(),
            conditions=qpe_exact.all_conditions() + [_phase_in_interval])

qpe_exact_with_extra_cond:  ⊢  

This has an extra condition that we will eliminate as redundant

Specifically, $\varphi \in [0, 1)$ is redundant given $2^t \varphi \in \{0 .. 2^t - 1\}$.

desired_phase_cond = qpe_exact.instance_expr.instance_expr.instance_expr.condition

desired_phase_cond:

defaults.assumptions = qpe_exact.all_conditions()[:-3] + [desired_phase_cond]

defaults.assumptions:

phase_cond = qpe_exact.all_conditions()[-2]

phase_cond:

phase_cond_lower_bound = phase_cond.derive_element_lower_bound()

phase_cond_lower_bound: ,  ⊢  

phase_cond_lower_bound.divide_both_sides(Exp(two, t))

,  ⊢  

phase_cond_upper_bound_01 = phase_cond.derive_element_upper_bound()

phase_cond_upper_bound_01: ,  ⊢  

phase_cond_upper_bound_02 = phase_cond_upper_bound_01.divide_both_sides(
    Exp(two, t)).inner_expr().rhs.distribute()

phase_cond_upper_bound_02: ,  ⊢  

inv_two_pow_t_is_pos = greater(phase_cond_upper_bound_02.rhs.operands[1].operand, zero).prove()

inv_two_pow_t_is_pos:  ⊢  

phase_cond_upper_bound_02.rhs.deduce_bound(inv_two_pow_t_is_pos)

 ⊢  

_phase_in_interval.literals_as_variables(_phase, _t).prove()

,  ⊢  

Now we can replace the $\varphi$ condition with the right one

phase_cond = qpe_exact_with_extra_cond.instance_expr.instance_expr.instance_expr.condition.prove()

phase_cond: ,  ⊢  

qpe_exact_with_extra_cond.instance_expr.instance_expr.instance_expr.operand.body

conditional = qpe_exact_with_extra_cond.instance_expr.instance_expr.instance_expr.operand.body

conditional:

cond_equiv = Iff(phase_cond.expr, desired_phase_cond).prove(assumptions=qpe_exact.all_conditions()[:-3])

cond_equiv:  ⊢  

defaults.assumptions = []

defaults.assumptions:

qpe_exact_done = (qpe_exact_with_extra_cond.inner_expr().instance_expr.instance_expr
                  .instance_expr.operand.body.substitute_condition(cond_equiv, assumptions=[]))

qpe_exact_done:  ⊢  

qpe_exact has been proven.  Now simply execute "%qed".

%qed

proveit.physics.quantum.QPE.qpe_exact has been proven.

	step type	requirements	statement
0	instantiation	1, 2, 3	⊢
	: , :
1	theorem		⊢
	proveit.logic.equality.rhs_via_equality
2	literal generalization	4	⊢
3	instantiation	21, 5, 6*, 7*	⊢
	: , : , :
4	instantiation	8, 15, 9*, 10*	⊢
	:
5	modus ponens	11, 12	⊢
6	instantiation	13, 160	⊢
	: , :
7	instantiation	13, 160	⊢
	: , :
8	conjecture		⊢
	proveit.physics.quantum.QPE._outcome_prob
9	modus ponens	14, 15	⊢
10	instantiation	92, 16, 17	⊢
	: , : , :
11	instantiation	18, 19	⊢
	: , : , : , : , : , : , :
12	generalization	20	⊢
13	conjecture		⊢
	proveit.core_expr_types.conditionals.satisfied_condition_reduction
14	conjecture		⊢
	proveit.physics.quantum.QPE._alpha_ideal_case
15	assumption		⊢
16	instantiation	21, 22	⊢
	: , : , :
17	instantiation	23, 24	⊢
	:
18	conjecture		⊢
	proveit.core_expr_types.lambda_maps.general_lambda_substitution
19	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat5
20	instantiation	25, 26	⊢
	: , : , :
21	axiom		⊢
	proveit.logic.equality.substitution
22	instantiation	27, 28	⊢
	:
23	conjecture		⊢
	proveit.numbers.exponentiation.exponentiated_one
24	instantiation	158, 128, 29	⊢
	: , : , :
25	axiom		⊢
	proveit.core_expr_types.conditionals.condition_replacement
26	instantiation	30, 31, 32	⊢
	: , :
27	conjecture		⊢
	proveit.numbers.absolute_value.abs_non_neg_elim
28	instantiation	33, 151	⊢
	:
29	instantiation	158, 141, 34	⊢
	: , : , :
30	theorem		⊢
	proveit.logic.booleans.implication.iff_intro
31	deduction	35	⊢
32	deduction	36	⊢
33	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_lower_bound
34	instantiation	158, 149, 154	⊢
	: , : , :
35	instantiation	41, 46, 37, 38, 39, 40	⊢
	: , :
36	instantiation	41, 42, 43, 118, 112, 44, 45	,  ⊢
	: , :
37	instantiation	54	⊢
	: , : , :
38	instantiation	130, 131, 46, 132, 47, 49	⊢
	: , : , : , : , :
39	instantiation	130, 151, 157, 48, 49	⊢
	: , : , : , : , :
40	instantiation	130, 157, 151, 51, 49	⊢
	: , : , : , : , :
41	conjecture		⊢
	proveit.logic.booleans.conjunction.and_if_all
42	conjecture		⊢
	proveit.numbers.numerals.decimals.nat4
43	instantiation	50	⊢
	: , : , : , :
44	instantiation	130, 157, 131, 51, 132, 134	⊢
	: , : , : , : , :
45	instantiation	52, 82, 99, 118, 53	,  ⊢
	: , : , :
46	conjecture		⊢
	proveit.numbers.numerals.decimals.nat3
47	instantiation	54	⊢
	: , : , :
48	instantiation	143	⊢
	: , :
49	assumption		⊢
50	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_4_typical_eq
51	instantiation	143	⊢
	: , :
52	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.in_IntervalCO
53	instantiation	55, 56, 57	,  ⊢
	: , :
54	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_3_typical_eq
55	theorem		⊢
	proveit.logic.booleans.conjunction.and_if_both
56	instantiation	72, 129, 82, 73, 58, 76, 59*, 77*	,  ⊢
	: , : , :
57	instantiation	60, 61, 62	,  ⊢
	: , : , :
58	instantiation	63, 123, 124, 112	,  ⊢
	: , : , :
59	instantiation	64, 117, 96	⊢
	:
60	conjecture		⊢
	proveit.numbers.ordering.transitivity_less_eq_less
61	instantiation	65, 66, 67	,  ⊢
	: , : , :
62	instantiation	68, 99, 69, 82, 70, 71*	⊢
	: , : , :
63	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_lower_bound
64	conjecture		⊢
	proveit.numbers.division.frac_zero_numer
65	theorem		⊢
	proveit.logic.equality.sub_right_side_into
66	instantiation	72, 129, 73, 74, 75, 76, 77*	,  ⊢
	: , : , :
67	instantiation	78, 117, 87, 96, 79*	⊢
	: , : , :
68	conjecture		⊢
	proveit.numbers.addition.strong_bound_via_right_term_bound
69	instantiation	80, 83	⊢
	:
70	instantiation	81, 82, 83, 84, 85*	⊢
	: , :
71	instantiation	86, 87	⊢
	:
72	conjecture		⊢
	proveit.numbers.division.weak_div_from_numer_bound__pos_denom
73	instantiation	158, 141, 88	,  ⊢
	: , : , :
74	instantiation	158, 141, 89	⊢
	: , : , :
75	instantiation	90, 123, 124, 112	,  ⊢
	: , : , :
76	instantiation	91, 146	⊢
	:
77	instantiation	92, 93, 94	,  ⊢
	: , : , :
78	conjecture		⊢
	proveit.numbers.division.distribute_frac_through_subtract
79	instantiation	95, 117, 96	⊢
	:
80	conjecture		⊢
	proveit.numbers.negation.real_closure
81	conjecture		⊢
	proveit.numbers.negation.negated_strong_bound
82	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.zero_is_real
83	instantiation	158, 141, 97	⊢
	: , : , :
84	instantiation	98, 109	⊢
	:
85	conjecture		⊢
	proveit.numbers.negation.negated_zero
86	conjecture		⊢
	proveit.numbers.addition.elim_zero_right
87	instantiation	158, 128, 99	⊢
	: , : , :
88	instantiation	158, 149, 100	,  ⊢
	: , : , :
89	instantiation	158, 149, 124	⊢
	: , : , :
90	conjecture		⊢
	proveit.numbers.number_sets.integers.interval_upper_bound
91	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_is_pos
92	axiom		⊢
	proveit.logic.equality.equals_transitivity
93	instantiation	101, 102, 103, 106, 104*	,  ⊢
	: , : , :
94	instantiation	105, 106	⊢
	:
95	conjecture		⊢
	proveit.numbers.division.frac_cancel_complete
96	instantiation	107, 146	⊢
	:
97	instantiation	158, 108, 109	⊢
	: , : , :
98	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.positive_if_in_rational_pos
99	instantiation	158, 141, 110	⊢
	: , : , :
100	instantiation	158, 111, 112	,  ⊢
	: , : , :
101	conjecture		⊢
	proveit.numbers.division.frac_cancel_left
102	instantiation	158, 114, 113	⊢
	: , : , :
103	instantiation	158, 114, 115	⊢
	: , : , :
104	instantiation	116, 117	⊢
	:
105	conjecture		⊢
	proveit.numbers.division.frac_one_denom
106	instantiation	158, 128, 118	⊢
	: , : , :
107	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nonzero_if_is_nat_pos
108	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.rational_pos_within_rational
109	instantiation	119, 120, 121	⊢
	: , :
110	instantiation	158, 149, 145	⊢
	: , : , :
111	instantiation	122, 123, 124	⊢
	: , :
112	instantiation	130, 151, 134	⊢
	: , : , : , : , :
113	instantiation	158, 126, 125	⊢
	: , : , :
114	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_nonzero_within_complex_nonzero
115	instantiation	158, 126, 127	⊢
	: , : , :
116	conjecture		⊢
	proveit.numbers.multiplication.elim_one_right
117	instantiation	158, 128, 129	⊢
	: , : , :
118	instantiation	130, 131, 157, 132, 133, 134	⊢
	: , : , : , : , :
119	conjecture		⊢
	proveit.numbers.division.div_rational_pos_closure
120	instantiation	158, 135, 148	⊢
	: , : , :
121	instantiation	158, 135, 146	⊢
	: , : , :
122	conjecture		⊢
	proveit.numbers.number_sets.integers.int_interval_within_int
123	conjecture		⊢
	proveit.numbers.number_sets.integers.zero_is_int
124	instantiation	136, 150, 137	⊢
	: , :
125	instantiation	158, 139, 138	⊢
	: , : , :
126	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_nonzero_within_real_nonzero
127	instantiation	158, 139, 140	⊢
	: , : , :
128	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_within_complex
129	instantiation	158, 141, 142	⊢
	: , : , :
130	conjecture		⊢
	proveit.logic.booleans.conjunction.any_from_and
131	axiom		⊢
	proveit.numbers.number_sets.natural_numbers.zero_in_nats
132	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_len_0_typical_eq
133	instantiation	143	⊢
	: , :
134	assumption		⊢
135	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nat_pos_within_rational_pos
136	conjecture		⊢
	proveit.numbers.addition.add_int_closure_bin
137	instantiation	144, 145	⊢
	:
138	instantiation	158, 147, 146	⊢
	: , : , :
139	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nonzero_int_within_rational_nonzero
140	instantiation	158, 147, 148	⊢
	: , : , :
141	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_within_real
142	instantiation	158, 149, 150	⊢
	: , : , :
143	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_2_typical_eq
144	conjecture		⊢
	proveit.numbers.negation.int_closure
145	instantiation	158, 156, 151	⊢
	: , : , :
146	instantiation	152, 157, 155	⊢
	: , :
147	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_nonzero_int
148	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat1
149	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.int_within_rational
150	instantiation	153, 154, 155	⊢
	: , :
151	theorem		⊢
	proveit.numbers.numerals.decimals.nat1
152	conjecture		⊢
	proveit.numbers.exponentiation.exp_natpos_closure
153	conjecture		⊢
	proveit.numbers.exponentiation.exp_int_closure
154	instantiation	158, 156, 157	⊢
	: , : , :
155	instantiation	158, 159, 160	⊢
	: , : , :
156	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_within_int
157	conjecture		⊢
	proveit.numbers.numerals.decimals.nat2
158	theorem		⊢
	proveit.logic.sets.inclusion.superset_membership_from_proper_subset
159	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nat_pos_within_nat
160	assumption		⊢
*equality replacement requirements