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

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

from proveit import defaults
from proveit import b, m
from proveit.logic import Or, Equals, InSet
from proveit.numbers import zero, one, Integer, Neg, Abs, Mod, sqrd
from proveit.numbers.number_sets.real_numbers import pi_between_3_and_4
from proveit.physics.quantum.QPE import (
    _best_guarantee_delta_nonzero, _alpha_ideal_case, 
    _phase_is_real, _phase_in_interval,
    _b_round, _best_round_def, _best_round_is_int, _delta_b_round, _delta_b_def,
    _two_pow_t, _t_in_natural_pos, _two_pow_t_is_nat_pos)

%proving _best_guarantee

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

_best_guarantee_delta_nonzero

 ⊢  

four_over_pi_sqrd = _best_guarantee_delta_nonzero.consequent.rhs

four_over_pi_sqrd:

_alpha_ideal_case

 ⊢  

Show that when $\delta_{b_r}=0$ then $(2^t \varphi) \in \{0 .. 2^t - 1\}$

defaults.assumptions = [Equals(_delta_b_round, zero)]

defaults.assumptions:

_delta_b_def

 ⊢  

delta_b_definition = _delta_b_def.instantiate({b:_b_round})

delta_b_definition:  ⊢  

phase_rel_01 = _delta_b_def.instantiate({b:_b_round}).inner_expr().lhs.substitute(zero)

phase_rel_01:  ⊢  

phase_rel_02 = phase_rel_01.right_add_both_sides(phase_rel_01.rhs.operands[1].operand).derive_reversed()

phase_rel_02:  ⊢  

phase_rel_03 = phase_rel_02.left_mult_both_sides(_two_pow_t)

phase_rel_03:  ⊢  

_best_round_def

 ⊢  

InSet(phase_rel_03.lhs, Integer).prove()

 ⊢  

_phase_in_interval

 ⊢  

phase_lower_bound = _phase_in_interval.derive_element_lower_bound()

phase_lower_bound:  ⊢  

phase_lower_bound.left_mult_both_sides(_two_pow_t)

 ⊢  

phase_upper_bound = _phase_in_interval.derive_element_upper_bound()

phase_upper_bound:  ⊢  

scaled_phase_upper_bound = phase_upper_bound.left_mult_both_sides(_two_pow_t)

scaled_phase_upper_bound:  ⊢  

scaled_phase_upper_bound.add_right(Neg(one), strong=False)

 ⊢  

ideal_alpha_01 = _alpha_ideal_case.derive_consequent()

ideal_alpha_01:  ⊢  

Replace $2^t \varphi$ with $b_r~\textrm{mod}~2^t$ assuming $\delta_{b_r} = 0$

ideal_alpha_02 = phase_rel_03.sub_right_side_into(ideal_alpha_01)

ideal_alpha_02:  ⊢  

_alpha_ideal_case.antecedent

InSet(_b_round, _alpha_ideal_case.antecedent.domain).prove()

 ⊢  

b_r_mod__eq__br = Mod(_b_round, _two_pow_t).simplification()

b_r_mod__eq__br:  ⊢  

ideal_alpha_03 = b_r_mod__eq__br.sub_left_side_into(ideal_alpha_02)

ideal_alpha_03:  ⊢  

Now we can prove that $|\alpha_{b_r~\textrm{mod}~2^t}|^2 > 4/\pi^2$ whether or not $\delta_{b_r} = 0$

defaults.preserved_exprs={Abs(ideal_alpha_03.lhs), sqrd(Abs(ideal_alpha_03.lhs))}
ideal_alpha_03.abs_both_sides().square_both_sides()

 ⊢  

pi_between_3_and_4

 ⊢  

four_over_pi_sqrd_bound = four_over_pi_sqrd.deduce_bound(pi_between_3_and_4.operands[0].reversed())

four_over_pi_sqrd_bound:  ⊢  

from proveit.numbers import Less, num
Less(num(4), num(9)).prove().divide_both_sides(num(9))

 ⊢  

eq_or_not = Or(defaults.assumptions[0], _best_guarantee_delta_nonzero.antecedent)

eq_or_not:

defaults.assumptions = []
alpha_sqrd_bound = eq_or_not.derive_via_dilemma(_best_guarantee_delta_nonzero.consequent)

alpha_sqrd_bound:  ⊢  

_best_round_def.sub_right_side_into(alpha_sqrd_bound)

 ⊢  

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

%qed

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

	step type	requirements	statement
0	instantiation	1, 2, 3	⊢
	: , : , :
1	reference	190	⊢
2	instantiation	4, 15, 5, 6, 7, 8	⊢
	: , : , :
3	axiom		⊢
	proveit.physics.quantum.QPE._best_round_def
4	theorem		⊢
	proveit.logic.booleans.disjunction.singular_constructive_dilemma
5	instantiation	9	⊢
	: , :
6	instantiation	10, 11, 12	⊢
	: , :
7	deduction	13	⊢
8	conjecture		⊢
	proveit.physics.quantum.QPE._best_guarantee_delta_nonzero
9	conjecture		⊢
	proveit.logic.equality.not_equals_is_bool
10	theorem		⊢
	proveit.logic.equality.rhs_via_equality
11	instantiation	14, 15	⊢
	:
12	instantiation	228, 16	⊢
	: , : , :
13	instantiation	44, 17, 18	⊢
	: , : , :
14	conjecture		⊢
	proveit.logic.booleans.unfold_is_bool
15	instantiation	19	⊢
	: , :
16	instantiation	162, 20	⊢
	: , :
17	instantiation	21, 22, 23, 24, 61	⊢
	: , : , :
18	instantiation	146, 25, 26	⊢
	: , : , :
19	axiom		⊢
	proveit.logic.equality.equality_in_bool
20	instantiation	27	⊢
	: , :
21	conjecture		⊢
	proveit.numbers.division.strong_div_from_denom_bound__all_pos
22	instantiation	254, 29, 28	⊢
	: , : , :
23	instantiation	254, 29, 30	⊢
	: , : , :
24	instantiation	31, 32, 33	⊢
	:
25	instantiation	34, 66, 94, 35, 60, 36*	⊢
	: , : , :
26	instantiation	37, 73, 38, 222, 39, 40*	⊢
	: , : , :
27	axiom		⊢
	proveit.logic.equality.not_equals_def
28	instantiation	254, 42, 41	⊢
	: , : , :
29	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_pos_within_real_pos
30	instantiation	254, 42, 71	⊢
	: , : , :
31	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.pos_real_is_real_pos
32	instantiation	43, 74, 195	⊢
	: , :
33	instantiation	44, 45	⊢
	: , : , :
34	conjecture		⊢
	proveit.numbers.division.strong_div_from_numer_bound__pos_denom
35	instantiation	46, 94, 158, 47, 48, 49*, 50*	⊢
	: , : , :
36	instantiation	51, 52, 53	⊢
	:
37	conjecture		⊢
	proveit.numbers.exponentiation.exp_eq_real
38	instantiation	254, 54, 55	⊢
	: , : , :
39	instantiation	56, 68, 207, 84, 57*	⊢
	: , :
40	instantiation	58, 59	⊢
	:
41	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat4
42	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nat_pos_within_rational_pos
43	conjecture		⊢
	proveit.numbers.exponentiation.exp_real_closure_nat_power
44	axiom		⊢
	proveit.numbers.ordering.transitivity_less_less
45	instantiation	131, 60, 61	⊢
	: , :
46	conjecture		⊢
	proveit.numbers.addition.strong_bound_via_left_term_bound
47	instantiation	254, 233, 62	⊢
	: , : , :
48	instantiation	160, 63	⊢
	:
49	instantiation	190, 64, 65	⊢
	: , : , :
50	conjecture		⊢
	proveit.numbers.numerals.decimals.add_5_4
51	conjecture		⊢
	proveit.numbers.division.frac_cancel_complete
52	instantiation	254, 244, 66	⊢
	: , : , :
53	instantiation	251, 71	⊢
	:
54	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.real_nonneg_within_real
55	instantiation	67, 68	⊢
	:
56	conjecture		⊢
	proveit.numbers.absolute_value.abs_eq
57	instantiation	69, 70	⊢
	:
58	conjecture		⊢
	proveit.numbers.exponentiation.exponentiated_one
59	instantiation	254, 244, 73	⊢
	: , : , :
60	instantiation	160, 71	⊢
	:
61	instantiation	72, 73, 114, 74, 75, 76, 77*	⊢
	: , : , :
62	instantiation	254, 249, 78	⊢
	: , : , :
63	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat5
64	instantiation	79, 81	⊢
	:
65	instantiation	80, 81, 82	⊢
	: , :
66	instantiation	254, 233, 83	⊢
	: , : , :
67	conjecture		⊢
	proveit.numbers.absolute_value.abs_complex_closure
68	instantiation	146, 207, 84	⊢
	: , : , :
69	conjecture		⊢
	proveit.numbers.absolute_value.abs_non_neg_elim
70	instantiation	99, 247	⊢
	:
71	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat9
72	conjecture		⊢
	proveit.numbers.exponentiation.exp_pos_less
73	instantiation	254, 233, 85	⊢
	: , : , :
74	instantiation	254, 86, 87	⊢
	: , : , :
75	instantiation	131, 88, 89	⊢
	: , :
76	instantiation	160, 103	⊢
	:
77	instantiation	173, 90, 91, 92	⊢
	: , : , : , :
78	instantiation	254, 246, 93	⊢
	: , : , :
79	conjecture		⊢
	proveit.numbers.addition.elim_zero_right
80	conjecture		⊢
	proveit.numbers.addition.commutation
81	instantiation	254, 244, 94	⊢
	: , : , :
82	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.zero_is_complex
83	instantiation	254, 249, 95	⊢
	: , : , :
84	instantiation	146, 96, 97	⊢
	: , : , :
85	instantiation	254, 249, 98	⊢
	: , : , :
86	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.real_pos_within_real
87	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.pi_is_real_pos
88	instantiation	99, 134	⊢
	:
89	instantiation	100, 101	⊢
	: , :
90	instantiation	102, 103, 104	⊢
	: , :
91	instantiation	105, 195, 106, 107, 108	⊢
	: , : , : , :
92	conjecture		⊢
	proveit.numbers.numerals.decimals.mult_3_3
93	conjecture		⊢
	proveit.numbers.numerals.decimals.nat5
94	instantiation	254, 233, 109	⊢
	: , : , :
95	instantiation	254, 246, 110	⊢
	: , : , :
96	instantiation	190, 111, 147	⊢
	: , : , :
97	instantiation	112, 256, 113	⊢
	: , :
98	instantiation	254, 246, 195	⊢
	: , : , :
99	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_lower_bound
100	theorem		⊢
	proveit.logic.booleans.conjunction.left_from_and
101	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.pi_between_3_and_4
102	conjecture		⊢
	proveit.numbers.exponentiation.exp_nat_pos_expansion
103	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat2
104	instantiation	254, 244, 114	⊢
	: , : , :
105	conjecture		⊢
	proveit.core_expr_types.operations.operands_substitution_via_tuple
106	instantiation	115, 195	⊢
	: , :
107	instantiation	210	⊢
	: , :
108	instantiation	116	⊢
	:
109	instantiation	254, 249, 117	⊢
	: , : , :
110	conjecture		⊢
	proveit.numbers.numerals.decimals.nat9
111	modus ponens	118, 119	⊢
112	conjecture		⊢
	proveit.numbers.modular.int_mod_elimination
113	instantiation	123, 124, 125, 248, 120	⊢
	: , : , :
114	instantiation	254, 233, 121	⊢
	: , : , :
115	conjecture		⊢
	proveit.core_expr_types.tuples.range_from1_len_typical_eq
116	conjecture		⊢
	proveit.numbers.numerals.decimals.reduce_2_repeats
117	instantiation	254, 246, 122	⊢
	: , : , :
118	conjecture		⊢
	proveit.physics.quantum.QPE._alpha_ideal_case
119	instantiation	123, 124, 125, 140, 126	⊢
	: , : , :
120	instantiation	131, 127, 128	⊢
	: , :
121	instantiation	254, 249, 129	⊢
	: , : , :
122	conjecture		⊢
	proveit.numbers.numerals.decimals.nat4
123	conjecture		⊢
	proveit.numbers.number_sets.integers.in_interval
124	conjecture		⊢
	proveit.numbers.number_sets.integers.zero_is_int
125	instantiation	130, 250, 166	⊢
	: , :
126	instantiation	131, 132, 133	⊢
	: , :
127	instantiation	190, 132, 147	⊢
	: , : , :
128	instantiation	190, 133, 147	⊢
	: , : , :
129	instantiation	254, 246, 134	⊢
	: , : , :
130	conjecture		⊢
	proveit.numbers.addition.add_int_closure_bin
131	theorem		⊢
	proveit.logic.booleans.conjunction.and_if_both
132	instantiation	135, 245, 158, 213, 136, 137, 138*	⊢
	: , : , :
133	instantiation	139, 140, 250, 166, 141, 142	⊢
	: , : , :
134	conjecture		⊢
	proveit.numbers.numerals.decimals.nat3
135	conjecture		⊢
	proveit.numbers.multiplication.weak_bound_via_right_factor_bound
136	instantiation	143, 158, 222, 159	⊢
	: , : , :
137	instantiation	144, 150	⊢
	: , :
138	instantiation	145, 238	⊢
	:
139	conjecture		⊢
	proveit.numbers.ordering.less_add_right_weak_int
140	instantiation	146, 248, 147	⊢
	: , : , :
141	instantiation	148, 245, 213, 222, 149, 150, 221*	⊢
	: , : , :
142	instantiation	151, 152, 153	⊢
	: , :
143	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.interval_co_lower_bound
144	conjecture		⊢
	proveit.numbers.ordering.relax_less
145	conjecture		⊢
	proveit.numbers.multiplication.mult_zero_right
146	theorem		⊢
	proveit.logic.equality.sub_left_side_into
147	instantiation	154, 245, 213, 224, 155, 156*	⊢
	: , : , :
148	conjecture		⊢
	proveit.numbers.multiplication.strong_bound_via_right_factor_bound
149	instantiation	157, 158, 222, 159	⊢
	: , : , :
150	instantiation	160, 256	⊢
	:
151	conjecture		⊢
	proveit.numbers.ordering.relax_equal_to_less_eq
152	instantiation	254, 233, 161	⊢
	: , : , :
153	instantiation	214	⊢
	:
154	conjecture		⊢
	proveit.numbers.multiplication.left_mult_eq_real
155	instantiation	162, 163	⊢
	: , :
156	instantiation	190, 164, 165	⊢
	: , : , :
157	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.interval_co_upper_bound
158	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.zero_is_real
159	axiom		⊢
	proveit.physics.quantum.QPE._phase_in_interval
160	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.natural_pos_is_pos
161	instantiation	254, 249, 166	⊢
	: , : , :
162	theorem		⊢
	proveit.logic.equality.equals_reversal
163	instantiation	167, 234, 178, 168, 179, 169*, 170*	⊢
	: , : , :
164	instantiation	190, 171, 172	⊢
	: , : , :
165	instantiation	173, 174, 175, 176	⊢
	: , : , : , :
166	instantiation	177, 239	⊢
	:
167	conjecture		⊢
	proveit.numbers.addition.right_add_eq_rational
168	instantiation	190, 178, 179	⊢
	: , : , :
169	instantiation	180, 212	⊢
	:
170	instantiation	218, 181, 182	⊢
	: , : , :
171	instantiation	183, 207, 208, 184, 185	⊢
	: , : , : , : , :
172	instantiation	218, 186, 187	⊢
	: , : , :
173	conjecture		⊢
	proveit.logic.equality.four_chain_transitivity
174	instantiation	228, 188	⊢
	: , : , :
175	instantiation	228, 189	⊢
	: , : , :
176	instantiation	237, 208	⊢
	:
177	conjecture		⊢
	proveit.numbers.negation.int_closure
178	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.zero_is_rational
179	instantiation	190, 191, 192	⊢
	: , : , :
180	conjecture		⊢
	proveit.numbers.addition.elim_zero_left
181	instantiation	193, 194, 195, 247, 196, 197, 200, 198, 212	⊢
	: , : , : , : , : , :
182	instantiation	199, 212, 200, 201	⊢
	: , : , :
183	conjecture		⊢
	proveit.numbers.division.mult_frac_cancel_numer_left
184	instantiation	254, 203, 202	⊢
	: , : , :
185	instantiation	254, 203, 204	⊢
	: , : , :
186	instantiation	228, 205	⊢
	: , : , :
187	instantiation	228, 206	⊢
	: , : , :
188	instantiation	230, 207	⊢
	:
189	instantiation	230, 208	⊢
	:
190	theorem		⊢
	proveit.logic.equality.sub_right_side_into
191	instantiation	209, 248	⊢
	:
192	assumption		⊢
193	conjecture		⊢
	proveit.numbers.addition.disassociation
194	axiom		⊢
	proveit.numbers.number_sets.natural_numbers.zero_in_nats
195	conjecture		⊢
	proveit.numbers.numerals.decimals.nat2
196	conjecture		⊢
	proveit.core_expr_types.tuples.tuple_len_0_typical_eq
197	instantiation	210	⊢
	: , :
198	instantiation	211, 212	⊢
	:
199	conjecture		⊢
	proveit.numbers.addition.subtraction.add_cancel_triple_32
200	instantiation	254, 244, 213	⊢
	: , : , :
201	instantiation	214	⊢
	:
202	instantiation	254, 216, 215	⊢
	: , : , :
203	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_nonzero_within_complex_nonzero
204	instantiation	254, 216, 217	⊢
	: , : , :
205	instantiation	218, 219, 220	⊢
	: , : , :
206	instantiation	228, 221	⊢
	: , : , :
207	instantiation	254, 244, 222	⊢
	: , : , :
208	instantiation	254, 244, 223	⊢
	: , : , :
209	axiom		⊢
	proveit.physics.quantum.QPE._delta_b_def
210	conjecture		⊢
	proveit.numbers.numerals.decimals.tuple_len_2_typical_eq
211	conjecture		⊢
	proveit.numbers.negation.complex_closure
212	instantiation	254, 244, 224	⊢
	: , : , :
213	conjecture		⊢
	proveit.physics.quantum.QPE._phase_is_real
214	axiom		⊢
	proveit.logic.equality.equals_reflexivity
215	instantiation	254, 226, 225	⊢
	: , : , :
216	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_nonzero_within_real_nonzero
217	instantiation	254, 226, 227	⊢
	: , : , :
218	axiom		⊢
	proveit.logic.equality.equals_transitivity
219	instantiation	228, 229	⊢
	: , : , :
220	instantiation	230, 238	⊢
	:
221	instantiation	231, 238	⊢
	:
222	instantiation	254, 233, 232	⊢
	: , : , :
223	instantiation	254, 233, 241	⊢
	: , : , :
224	instantiation	254, 233, 234	⊢
	: , : , :
225	instantiation	254, 235, 256	⊢
	: , : , :
226	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.nonzero_int_within_rational_nonzero
227	instantiation	254, 235, 236	⊢
	: , : , :
228	axiom		⊢
	proveit.logic.equality.substitution
229	instantiation	237, 238	⊢
	:
230	conjecture		⊢
	proveit.numbers.division.frac_one_denom
231	conjecture		⊢
	proveit.numbers.multiplication.elim_one_right
232	instantiation	254, 249, 239	⊢
	: , : , :
233	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.rational_within_real
234	instantiation	240, 241, 242, 243	⊢
	: , :
235	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_nonzero_int
236	conjecture		⊢
	proveit.numbers.numerals.decimals.posnat1
237	conjecture		⊢
	proveit.numbers.multiplication.elim_one_left
238	instantiation	254, 244, 245	⊢
	: , : , :
239	instantiation	254, 246, 247	⊢
	: , : , :
240	conjecture		⊢
	proveit.numbers.division.div_rational_closure
241	instantiation	254, 249, 248	⊢
	: , : , :
242	instantiation	254, 249, 250	⊢
	: , : , :
243	instantiation	251, 256	⊢
	:
244	conjecture		⊢
	proveit.numbers.number_sets.complex_numbers.real_within_complex
245	instantiation	252, 253, 256	⊢
	: , : , :
246	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_within_int
247	theorem		⊢
	proveit.numbers.numerals.decimals.nat1
248	conjecture		⊢
	proveit.physics.quantum.QPE._best_round_is_int
249	conjecture		⊢
	proveit.numbers.number_sets.rational_numbers.int_within_rational
250	instantiation	254, 255, 256	⊢
	: , : , :
251	conjecture		⊢
	proveit.numbers.number_sets.natural_numbers.nonzero_if_is_nat_pos
252	theorem		⊢
	proveit.logic.sets.inclusion.unfold_subset_eq
253	instantiation	257, 258	⊢
	: , :
254	theorem		⊢
	proveit.logic.sets.inclusion.superset_membership_from_proper_subset
255	conjecture		⊢
	proveit.numbers.number_sets.integers.nat_pos_within_int
256	conjecture		⊢
	proveit.physics.quantum.QPE._two_pow_t_is_nat_pos
257	theorem		⊢
	proveit.logic.sets.inclusion.relax_proper_subset
258	conjecture		⊢
	proveit.numbers.number_sets.real_numbers.nat_pos_within_real
*equality replacement requirements