-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdissertation.tex
5342 lines (4950 loc) · 303 KB
/
dissertation.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% LyX 2.3.2-2 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[11pt]{iuphd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fontspec}
\setmainfont[Mapping=tex-text]{Times New Roman}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{verbatim}
\usepackage{rotfloat}
\usepackage{booktabs}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{enumitem}
\usepackage{pdfpages}
\usepackage{graphicx}
\usepackage{setspace}
\usepackage[all]{xy}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
\let\@@LyX\LyX
\def\LyX{\@ensure@LTR{\@@LyX}}
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}
%% A simple dot to overcome graphicx limitations
\newcommand{\lyxdot}{.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newlength{\lyxlabelwidth} % auxiliary length
\providecommand*{\code}[1]{\texttt{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{csquotes}
\usepackage{comment}
\usepackage{framed}
\usepackage{mathrsfs}
\usepackage{setspace}
\usepackage{dsfont}
\usepackage[AutoFallBack=true]{xeCJK}
\setCJKmainfont[FallBack=Batang]{SimSun}
% \usepackage{xeCJK}
% \setCJKmainfont{SimSun}
\usepackage[all]{xy}
\newcommand{\xyR}[1]{\xymatrixrowsep={#1}}
\newcommand{\xyC}[1]{\xymatrixcolsep={#1}}
%\usepackage[basic]{complexity}
\newcommand{\lang}[1]{{\ensuremath{\textsf{#1}}}}
\newcommand{\newlang}[2]{\newcommand{#1}{\lang{#2}}}
\newlang{\usat}{UNIQUE-SAT}
\newcommand{\ComplexityFont}[1]{%
{\ensuremath{\textsf{#1}}}%extra {} makes everyone happy.
}
\newcommand{\NP}{\ComplexityFont{NP}}
\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem{prop}{Proposition}[chapter]
\newtheorem{thm}{Theorem}[chapter]
\newtheorem{lemma}{Lemma}[chapter]
\newtheorem{case}{Case}
\newtheorem{corollary}{Corollary}[chapter]
\theoremstyle{definition}
\newtheorem{definition}{Definition}[chapter]
\newtheorem{question}{Question}[chapter]
\newtheorem*{method}{Method}
\newtheorem{example}{Example}[chapter]
\newtheorem{postulate}{Postulate}[chapter]
\usepackage[braket,qm]{qcircuit}
\newcommand{\proj}[1]{\op{#1}{#1}}
\usepackage{unicode-math}
\RequirePackage{ifthen}
\@ifpackageloaded{unicode-math}{}{
\newcommand{\symbf}{\mathbf}
\newcommand{\symrm}{\mathrm}
\newcommand{\symcal}{\mathcal}
\newcommand{\symbb}{\mathbb}
}
\newcommand{\muB}{\ensuremath{\mu^{\symrm{B}}}}
\newcommand{\muC}{\ensuremath{\mu^{\symrm{C}}}}
\newcommand{\muF}{\ensuremath{\mu^{\symrm{F}}}}
\newcommand{\symrmL}{\ensuremath{\symrm{L}}}
\newcommand{\symrmR}{\ensuremath{\symrm{R}}}
\newcommand{\mul}[1][]{\ensuremath{\mu^{\symrmL{#1}}}}
\newcommand{\mur}[1][]{\ensuremath{\mu^{\symrmR{#1}}}}
\newcommand{\barmuD}{\ensuremath{\bar{\mu}^{\symrm{D}}}}
\newcommand{\events}{\ensuremath{\symcal{E}}}
\newcommand{\eventsC}{\ensuremath{\events_{\symrm{C}}}}
\newcommand{\set}[2]{\ensuremath{\left\{ {#1}\mathrel{}\middle|\mathrel{}{#2}\right\} }}
\newcommand{\gmult}{*}
\newcommand{\Fpx}[1]{\symbb{F}_{{#1}}}
\newcommand{\Fp}{\Fpx{p}}
\newcommand{\Fppx}[1]{\Fpx{{#1}^2}}
\newcommand{\Fpp}{\Fppx{p}}
\newcommand{\Fq}{\Fpx{q}}
\newcommand{\ff}[1]{\Fpx{#1}}
\newcommand{\ffzx}[2]{\Fpx{#1}^{{#2}\;*}}
\newcommand{\ffx}[2]{\Fpx{#1}^{{#2}}}
\newcommand{\ffzd}[1]{\ffzx{#1}{d}}
\newcommand{\ffd}[1]{\ffx{#1}{d}}
\newcommand{\VVec}[1]{\vec{\symbf{#1}}}
\newcommand{\mathReal}{\symbb{R}}
\newcommand{\mathComplex}{\symbb{C}}
\newcommand{\braket}[2]{\ip{#1}{#2}}
\newcommand{\todo}[1]{\textbf{TODO.~#1}}
\newcommand{\Eq}[1]{Eq.~(\ref{#1})}
\newcommand{\Sphere}[1]{\symbf{S}^{#1}}
\newcommand{\R}{\mathReal}
\newcommand{\rme}{\symrm{e}}
\newcommand{\rmi}{\symrm{i}}
\newcommand{\rmd}{\symrm{d}}
\newcommand{\CP}[1]{\mathComplex\symbf{P}^{#1}} % Complex projective space
\newcommand{\DCP}[1]{\symbf{D}\mathComplex\symbf{P}^{#1}} % Discrete complex projective
\def\fh{\mathfrak{h}}
\newcommand{\uf}{U_{\!f}}
\newcommand{\scalarPlus}{+}
\newcommand{\boolt}{\textsf{Bool}}
\newcommand{\bfalse}{\texttt{\textbf{false}}}
\newcommand{\btrue}{\texttt{\textbf{true}}}
\newcommand{\dotprod}{dot product}
\newcommand{\Tr}{\ensuremath{\mathop{\mathrm{Tr}}\nolimits}}
\newcommand{\Psibar}{\overline{\Psi}}
\newcommand{\cardp}[2]{#1 \, \slash\!\! \slash \, #2}
\def\round{\mathop{\rm round}\nolimits}
\newcommand{\ps}{\texttt{+}}
\newcommand{\ms}{\texttt{-}}
\newcommand{\Hilb}{\symcal{H}}
\newcommand{\coreBorn}{\ensuremath{\overline{\Hilb}}}
\def\C{{\symbb{C}}}
\newcommand{\ultramodular}{\symcal{M}}
\newcommand{\ultramodularL}[1][]{\ensuremath{\ultramodular^{L{#1}}}}
\newcommand{\ultramodularR}[1][]{\ensuremath{\ultramodular^{R{#1}}}}
\newcommand{\frameL}[1][]{\ensuremath{f^{L{#1}}}}
\newcommand{\frameR}[1][]{\ensuremath{f^{R{#1}}}}
\newcommand{\pmeas}{\ensuremath{\mu}}
\newcommand{\nb}{\nolinebreak[3] }
\NewDocumentCommand{\jthSubsystem}{m O{} m}{{#1}_{#2}^{#3}}
\newcommand{\interval}[1]{{\normalfont\textsf{\textbf{#1}}}}
\newcommand{\imposs}{\interval{F}}
\newcommand{\necess}{\interval{T}}
\newcommand{\unknown}{\interval{U}}
\usepackage{xparse}
\NewDocumentCommand{\fnorm}{s m}{\mathsf{N}\IfBooleanT{#1}{^{-1}}\left({#2}\right)}
\usepackage{refcount}
% https://tex.stackexchange.com/questions/16866/how-can-i-use-footnotemark-with-a-ref-argument
\department{Department of Mathematics}
\department{Department of Computer Science}
\usepackage{datetime2}
\usepackage{datetime2-calc}
\monthGranted{June}%\DTMmonthname{\month}}
\yearGranted{\the\year}
% https://wiki.lyx.org/LyX/Tables#tabularx
%% Hack by Heiko Oberdiek (on de.comp.text.tex)
\usepackage{tabularx}
%% Redefine the standard table
\let\ORIGtabular\tabular
\let\ORIGendtabular\endtabular
\let\ORIGtabularx\tabularx
\renewcommand*{\tabularx}{%
\def\tabular{%
\let\endtabular\ORIGendtabular
\ORIGtabular
}%
\ORIGtabularx
}
\renewcommand{\tabularxcolumn}[1]{m{#1}}
\newcolumntype{Y}{>{\centering\doublespacing\arraybackslash}X}
\newcolumntype{M}[1]{>{\centering\doublespacing\arraybackslash}m{\widthof{#1}}}
% https://tex.stackexchange.com/questions/19094/allowing-line-break-at-in-inline-math-mode-breaks-citations/19100#19100
\AtBeginDocument{%
\mathchardef\mathcomma\mathcode`\,
\mathcode`\,="8000
}
{\catcode`,=\active
\gdef,{\mathcomma\nolinebreak[3]}
}
\usepackage[font=doublespacing]{caption}
\newcommand{\PhD}{Ph.D.\ }
% \hyphenation{$D$=dimen-sional}
\@ifundefined{showcaptionsetup}{}{%
\PassOptionsToPackage{caption=false}{subfig}}
\usepackage{subfig}
\makeatother
\usepackage{polyglossia}
\setdefaultlanguage[variant=american]{english}
\setotherlanguage{arabic}
\setotherlanguage{bahasai}
\setotherlanguage{basque}
\setotherlanguage{french}
\setotherlanguage{german}
\setotherlanguage{italian}
\setotherlanguage{portuges}
\setotherlanguage{turkish}
\setotherlanguage{vietnamese}
\usepackage[style=numeric-comp,maxbibnames=10,doi=false,isbn=false,url=false]{biblatex}
\addbibresource{prop.bib}
\begin{document}
\title{Discrete Quantum Theories and Computing}
\author{Yu-Tsung Tai}
\maketitle
%data for Acceptance Page
\committeeMember{Amr A. Sabry, PhD} \committeeMember{Dylan Paul
Thurston, PhD} \committeeMember{Gerardo Ortiz, PhD} \committeeMember{Andrew
J. Hanson, PhD} \committeeMember{Shouhong Wang, PhD} \defensedate{November
29, 2018} \acceptancepage
%data for Copyright Page
%\copyrightpage
\begin{dedication}To my parents, Cheng-Tien Tai (戴振沺) and Feng-Ming
Chang (張鳳鳴).\end{dedication}
\begin{comment}
\chapter*{Survey of the acknowledgments in theses}
I found the sentences in my Acknowledgments almost always contains
“thank” and looks boring. To improve my Acknowledgments, I briefly
read the Acknowledgments in other theses \cite{Chih2013,Sun2015,Lee2013,Chen2016,sabry1995formal}.
\end{comment}
\begin{acknowledgments*}
\begin{sidewaystable}
\noindent \centering{}{\small{}\caption{\label{tab:committee}The professors served in all my committees.}
}%% ERT block 1 (before LyX tabular)
\renewcommand{\tabular}{\tabularx{\linewidth}}
\renewcommand{\endtabular}{\endtabularx}
{\small{}}%
\begin{tabular}{M{\small{}MATH-M781}M{\small{}Co-author}M{\small{}(\textarabic{عمرو~صبري})}M{\small{}Co-author}M{\small{}Thurston}M{\small{}Shouhong}M{\small{}Lawrence}Y}
\toprule
{\small{}Committee or course} & {\small{}Gerardo Ortiz} & {\small{}Amr\nolinebreak[3] A. Sabry\linebreak[3] (}\textarabic{{\small{}عمرو
صبري}}{\small{})} & {\small{}Andrew\nolinebreak[3] J. Hanson} & {\small{}Dylan\nolinebreak[3] Paul Thurston} & {\small{}Shouhong Wang\linebreak[3] (}{\small{}汪守宏}{\small{})} & {\small{}Lawrence\nolinebreak[3] S.\linebreak[2] Moss} & {\small{}Relation with the dissertation}\tabularnewline
\midrule
\midrule
& {\small{}Co-author} & {\small{}Co-author} & {\small{}Co-author} & & & & {\small{}Most of Chapters~\ref{chap:Conventional-Quantum-Theory},
\ref{chap:Unrestricted-Finite-Fields}, and~\ref{chap:DQT=000026DQC}
is based on~\cite{geometry2013} and~\cite{DQT2014}; most of Chapter~\ref{chap:QIVPM}
is based on~\cite{THOS2018}.}\tabularnewline
\midrule
{\small{}Research committee} & {\small{}Co-chair} & {\small{}Co-chair} & {\small{}Member} & {\small{}Co-chair} & {\small{}Member} & & {\small{}Some questions in the dissertation proposal are answered
in Chapter~\ref{chap:QIVPM}, and some of the remaining ones are
explained in Chapter~\ref{chap:Further-Discussion}.}\tabularnewline
\midrule
& & {\small{}Supervisor} & & & & & {\small{}The application for \emph{{\small{}Rethinking Foundations of Physics}}
2017 workshop inspires Chapter~\ref{chap:Introduction}.}\tabularnewline
\midrule
{\small{}Advisory committee} & {\small{}Member} & {\small{}Member} & {\small{}Member} & {\small{}Member} & & & {\small{}The survey of real computation in the Computer Science qualifying
exam (chaired by Prof.\ Sabry) inspires Chapter~\ref{chap:Introduction}.}\tabularnewline
\midrule
{\small{}PHYS-P700} & {\small{}Instructor} & & & & & & {\small{}The textbook~\cite{Mermin2007} of \emph{{\small{}Quantum Computation and Information}}
is cited in Chapters~\ref{chap:Introduction}, \ref{chap:Conventional-Quantum-Theory},
\ref{chap:DQT=000026DQC}, and~\ref{chap:QIVPM}.}\tabularnewline
\midrule
{\small{}CSCI-B629} & & {\small{}Instructor} & & & & & {\small{}The textbook~\cite{hottbook2013} of \emph{{\small{}Homotopy Type Theory}}
is cited in Sec.~\ref{discretequantumtheoryIIb}.}\tabularnewline
\midrule
{\small{}Tier 3 committee} & {\small{}Co-chair} & {\small{}Co-chair} & & {\small{}Member} & & {\small{}Co-chair} & {\small{}Two of the assigned papers \cite{Schumacher2012-SCHMQT,doi:10.1142/S0217984913500644}
in the Tier 3 exam~\cite{Mathematics2018} are cited in Chapters~\ref{chap:Introduction}
and~\ref{chap:Unrestricted-Finite-Fields}.}\tabularnewline
\midrule
{\small{}MATH-M781} & & & & & & {\small{}Instructor} & {\small{}The presented paper~\cite{Abramsky2012} of \emph{{\small{}Coalgebra}}
is cited in Sec.~\ref{subsec:Classical-and-Quantum}.}\tabularnewline
\bottomrule
\end{tabular}% ERT block 2 (after LyX tabular)
\renewcommand{\tabular}{\ORIGtabular}
\renewcommand{\endtabular}{\ORIGendtabular}
\end{sidewaystable}
I want to thank the professors who served in all my committees. These
professors advised me as committee members and taught me while we
wrote papers together and when I took their courses. Most of my dissertation
is either based on these papers or inspired by the studies supervised
by them as listed in Table~\ref{tab:committee}. Especially, Prof.\ Andrew
J. Hanson, Prof.\ Gerardo Ortiz, and Prof.\ Amr A. Sabry\ (\textarabic{عمرو صبري})
meet me weekly for the past few years, read and tried to understand
what I typed which sometimes even myself cannot understand, taught
me how to organize them in ``English'' so that general audience
might be interested and have some chance to understand, and encouraged
me to participate seminars, workshops, and conferences. Prof.\ Lawrence
Moss invited me to present our results in the interdisciplinary logic
seminar and theory seminar in Computer Science and wrote an assessment
letter for me. Although not directly related to this dissertation,
the \textgerman[variant=german,spelling=new,babelshorthands=true]{Weil}
conjecture~\cite{hartshorne1977algebraic} on Grassmannians studied
with Prof.\ Dylan Paul Thurston and the quantum interpretation discussed
with Prof.\ Shouhong Wang (汪守宏) also broadened my understanding on
discrete and conventional quantum theories. I would like to express
my appreciation to all of these.
To have the current content of dissertation, I would also like to
thank John Gardiner for some inspiring discussion about quantum probability
measures over finite fields~\cite{Gardiner2014}. His research supervised
by Prof.\ Gerardo Ortiz inspired Sec.~\ref{subsec:Maximal-entanglement}
and~\ref{sec:Toward-IVPM}. Besides of my committee members, what
I learned from the teachers in other courses also helped me consolidate
this dissertation as listed in Table~\ref{tab:teacher}. Learning
other materials also made me more mature and easier to communicate
with others. I need to thank those who taught me, especially my English
teachers, Traci Nagle, Elizabeth ``Betsy'' Merceron, and Kexin ``Casey''
Chen (谌可心).
\begin{table}[!t]
\begin{doublespace}
\noindent \centering{}\caption{\label{tab:teacher}Other courses I took which is relevant to this
dissertation, where IUB stands for Indiana University Bloomington
and NTU stands for National Taiwan University.}
%% ERT block 1 (before LyX tabular)
\renewcommand{\tabular}{\tabularx{\linewidth}}
\renewcommand{\endtabular}{\endtabularx}
\begin{tabular}{M{Chou~(周謀鴻)}cM{MATH-M522}Y}
\toprule
Instructor & School & Course & Relation with the dissertation\tabularnewline
\midrule
\midrule
Tom Lewis & IUB & SLST-T501 & Sec.~\ref{subsec:Discrete-Deutsch-algorithm} is based on the term
paper of \emph{Academic Writing}.\tabularnewline
\midrule
Michael\nolinebreak[3] A. Mandell & IUB & MATH-M522 & The textbook~\cite{Hatcher2001} of \emph{Topology II} is cited
in Chapters~\ref{chap:Introduction} and~\ref{chap:Conventional-Quantum-Theory}.\tabularnewline
\midrule
Steven Myers & IUB & CSCI-B502 & The textbook~\cite{AroraBarak2009} of \emph{Computational Complexity}
is cited in Sec.~\ref{modalquantumcomputing}.\tabularnewline
\midrule
Valery Lunts & IUB & MATH-M501 & The textbook~\cite{DummitFoote2004} of \emph{Survey of Algebra}
is cited in Secs.~\ref{sec:background}, \ref{discretequantumtheoryI},
and~\ref{discretequantumtheoryIIb}.\tabularnewline
\midrule
Huah Chu\linebreak[3] (朱樺\textenglish[variant=american]{)} & NTU & 221~U3830\linebreak[3] 221~U3840 & The textbook~\cite{Artin1991} of \emph{Algebra (I)} and \emph{(II)}
is cited in Secs.~\ref{subsec:Two-dimensional-Hilbert-Space}, \ref{subsec:Cyclic-Properties-of},
\ref{subsec:Complexified-Finite-Fields}, and~\ref{discretequantumtheoryIIb}.\tabularnewline
\midrule
Jin-Tzu Chen\linebreak[3] (陳金次) & NTU & 201~31300 & The textbook~\cite{GAMELIN2003} of \emph{Functions of a Complex Variable}
is cited in Sec.~\ref{subsec:Vector-Spaces}.\tabularnewline
\midrule
Mo-Hong\linebreak[3] Chou (周謀鴻) & NTU & 221~U4290 & The textbook~\cite{GolubVanLoan1996} of \emph{Introduction to Computational Linear Algebra}
is cited in Sec.~\ref{subsec:Finite-Precision-Extension-of}.\tabularnewline
\bottomrule
\end{tabular}% ERT block 2 (after LyX tabular)
\renewcommand{\tabular}{\ORIGtabular}
\renewcommand{\endtabular}{\ORIGendtabular}
\end{doublespace}
\end{table}
Many people have done everything to make my double-major smooth. I
need to thank all of their supports, financially or providing some
experience, as listed in my Curriculum Vitae at the end of the dissertation.
Most importantly, Prof.\ Amr A. Sabry\ (\textarabic{عمرو صبري})
helped me deal with the rules, supervised my reading courses for writing
our papers, and financially support me as a research assistant and
associate. In the department of Mathematics, I need to thank the directors
of graduate study in Mathematics, especially Prof.\ Christopher Judge,
Prof.\ Matthias Weber, and Prof.\ Michael A.\ Mandell; and the
graduate services assistant, Kate Forrest. In the department of Computer
Science, I want to thank the directors of \PhD study in Computer
Science, especially Prof.\ Yuqing Melanie Wu (吴愈青) and Prof.\ \textturkish{Funda
Ergun}; the graduate student office; the director of AI/UI assignments,
Charles Pope; and the infrastructure and technology group (ITG). Particularly,
I don't know how much computational power I consumed to count the
states in Sec.~\ref{subsec:Maximal-entanglement}. This computational
power not only came from the Linux systems in Computer Science but
also came from the Big Red II administrated by University Information
Technology Services (UITS). Indiana University Libraries was also
extremely helpful during my dissertation research. Except for a stack
of books I checked out directly, while the books are not in their
collection, I occasionally requested them via the Interlibrary Loan
service or recommended IU libraries to purchase them.
Except for the financial support via employment and award, I have
also supported by my family, especially my father Cheng-Tien Tai (戴振沺).
He always thinks one-step ahead and cares about my future more than
I do. Discussion with other family members and friends also helped
me to compose this dissertation, to do research, or to live better
in general, and I want to thank the following people which haven't
been listed previously:\footnote{For some of them, I only provide their Chinese names for two reasons.
First, I might only know their Chinese names. Second, there are many
ways to translate a name to English, but I don't know which one they
choose.}
\begin{itemize}
\item The \PhD students in Mathematics, including Kin Wai Chan,
ChunHsien Lu (呂俊賢), Cong Zhou (周蔥), Junyan Xu (许俊彦), Zhipeng Lu (路志鹏),
Robert Rose, Neal Coleman, Dami Lee, Ruiyu Yang (杨瑞雨), Yingwei Li
(李盈伟), Yu-Yuan Chen (陳裕元), Jan-Li Lin (林展立), Ping Zhong, Chen Xu (徐晨),
Yiqiu Mao (茅一遒), Yu-Min Chung (鍾佑民), Shizhuo Zhang (张诗卓), Max Yining
Zhang (张忆宁), \textturkish{Ata Tuncer}, Hongming Nie (聂洪明), Sandeep
Bhupatiraju, Peng Wang, Guanglu Zhu (祝广路), Sailaja Gajula, Xuqiang
Qin (秦绪强), and \textvietnamese{Phuong Nguyen}, \ldots , etc.
\item Other members in Mathematics, including Weihua Liu (刘伟华),
Yinan ``Christina'' Wu (武怡楠), Cheng ``Freddie'' Shi (史程), Shabnam
Kavousian, and Tyler Bennett (班天瑞), \ldots , etc.
\item My officemates, especially, Inhak Hwang\ (황인학), Jiecao
Chen (陈洁操), Erfan Sadeqi~Azer, Chao ``Alan'' Tao (陶超), Haoyu Zhang
(张皓宇), Yadi Wei (魏雅廸), BoLi Fang (方博立), Yuan Xie (谢缘), and Mrinmoy
Maity, \ldots , etc.
\item My other friends having an office in Lindley or \textportuges{Luddy}
Hall, especially, Prof.~Daniel Leivant, Prof.~Paul Purdom, Prof.~Chung-Chieh
Shan (單中杰), Chao-Hong Chen (陳昭宏), Robert Rose, \textbasque{Bibrak
Chandio}, Yuxiang Jiang (蒋宇翔), Lei Wang (王磊), Diyue Bu (卜廸悦), Pei-Ying
Chen (陳珮瑩), Prof.~Qin Zhang (张勤), Praveen Narayanan, Liang Chen (陈亮),
\textfrench{Ambrose Bonnaire-Sergeant}, Ali Varamesh, Min-Chin Lin
(林旻瑾), and Career Services in the School of Informatics, Computing,
and Engineering, \ldots , etc.
\item My other family members, including my mother Feng-Ming Chang
(張鳳鳴), my grandmothers 戴許玉婷 and 張林枝, my sister Sih-Sian Tai (戴司嫻),
my cousins especially Caren Liu (劉鈺平) and Kiwi Liu (劉子綺), and my
aunts and uncles, \ldots , etc.
\item My roommates, including Meng-Wei Chen (陳孟瑋), Yu ``Larry''
Chen (陈煜), Kenshin Reita (禮田謙信), and Jing-Han Liou (劉經翰).
\item My classmates or friends in NTU, including Hao-Chun Lee (李浩君),
Hsien-Ching Kao (高憲慶), Wei Cheng (鄭維), Chin-Yi Lin (林金毅), Chun-Ting
Chen (陳俊廷), and Prof.~Chen-Ying Huang (黃貞穎), \ldots , etc.
\item My friends living in the Tulip Tree Apartments, including Chao-Hong
Chen (陳昭宏), Tsaiyi Wu (吳采奕), Cheng ``Freddie'' Shi (史程), Ossama
Abdel~Gawwad, and Cathryn ``Cathy'' Creger-Chambers, \textbahasai{Sary
Silvhiany}, Shaozhuan Li (李绍颛), Chenwei Zhang (张晨薇), Shu-Han ``Nancy''
Chang (張舒涵), and Ching-Chi ``Victoria'' Chang (張靖琪), \ldots , etc.
\item My AT\&T family plan members, especially Meng-Wei Chen (陳孟瑋),
Yao-Yu Chih (池耀宇), and Xinyi ``Diana'' Gong (龚欣怡), \ldots , etc.
\item Other friends, including Shu-Ling Wang (王舒齡), Wanling ``Wynnie''
Chang (張婉鈴), Yu-Jung Lin (林宇容), Winnie Lou (何慧芳), Yi-Rong Yang (楊宜蓉),
Yi-Chu Chang (張逸竹), Jim \textgerman[variant=german,spelling=new,babelshorthands=true]{Zimmerly},
Peng Chou ``Davis'' Chen (陳鵬舟), Zihang Shao (邵子航), Prof.~Ying Ding
(丁颖), Hung-Chun Chao (趙竑鈞), Guang Zuo (左光), Prof.~Jung-Chao Ban (班榮超),
Prof.~Jyh-Chyi Gong (龔治齊), 江靜宜, and the office of International Services\ldots ,
etc.
\end{itemize}
\noindent This list could be on and on and never ends. If you have
helped me in any form or provide any helpful information during my
\PhD study, but I forget to list you or your unit here. Please forgive
my bad memory.
Finally, I want to thank K9 Web Protection for blocking distractive
websites to keep me focus, and Jin-Ru Yang (楊謹如) for keeping the password
and helping me control myself in general.\end{acknowledgments*}
\begin{preface*}
\begin{itemize}
\item The latest PDF version of this thesis is in GitHub: \url{https://git.io/fxbuG}~.
\item Its source code is typeset using \LyX{} \cite{LyX} in \url{https://git.io/fxbuE}
and the exported \LaTeX{} file is in \url{https://git.io/fhZBW}~.
\item Any comments can be left in the Issue part of the GitHub repository:
\url{https://git.io/fxbug}~.
\end{itemize}
The following explains how to compile the PDF file from the \LaTeX{}
source:
\begin{enumerate}
\item \label{enu:Clone-the-git}Clone the git repository of this thesis
\url{https://git.io/fhZP5} into your local directory and the thesis
document class \url{https://github.com/yuttai/iuphd} in a location
where the system can find.
\item In the local directory of this thesis, run \code{xelatex dissertation.tex}~.
\item Run \code{biber dissertation}~.
\item Run \code{xelatex dissertation.tex} several times until all the references
are resolved.
\end{enumerate}
The previous steps only tested in Microsoft Windows with MiK\TeX{}
2.9. Please report me if there is any difficulty to compile it. Besides,
to compile a PDF file from the \LyX{} source, just finish step~\ref{enu:Clone-the-git},
open \code{dissertation.lyx} in \LyX , and click the toolbar button
\includegraphics[width=1em]{buffer-view}.\end{preface*}
\begin{abstract*}Most quantum computing models are based on the continuum
of real numbers, while classical digital computers faithfully realize
only discrete computational models. Analog computers appear to be
an option, but in reality are far weaker than would be needed for
computational models requiring real numbers. One approach to resolving
this conflict is to find consistent mathematical ways to limit measurement
precision to computable contexts that do not require incomputable
real numbers. Our goal is to build a more philosophically consistent
models by investigating discrete quantum computing using finite number
systems, and, alternatively, by incorporating finite precision measurement
using intervals into quantum theory.
We begin by replacing the continuum of complex numbers by discrete
finite fields in quantum theory. The simplest theory, defined over
unrestricted finite fields, is so weak that it cannot express Deutsch's
algorithm, but, paradoxically, is also so powerful that it can be
used to solve the $\usat$ problem, which is as hard as a general
$\NP$-complete problem.
Our second framework employs only finite fields over prime numbers
of the form $4\ell+3$, which possess no solutions to $x^{2}+1=0$,
and thus permit an elegant complex representation of the finite field
by adjoining $\rmi=\sqrt{-1}$. Because the states of a discrete $n$-qubit
system are in principle enumerable, we can count the number of states,
and determine the proportions of entangled and unentangled states.
Depending on how we model the measurement process, this improved framework
can be used to implement deterministic Deutsch's algorithm and the
probabilistic Grover search algorithm in a local region, but we still
haven't found a consistent way to treat quantum probability measures
in general.
Finally, we shift our attention to consider quantum interval-valued
probability measures (IVPMs), which potentially embody both finite
precision measurement and a sensible correspondence to standard quantum
probability. This interval-valued framework not only provides a natural
generalization of both classical IVPMs and conventional quantum probability
measures, but also allows us to establish bounds on the validity of
the Kochen-Specker and Gleason theorems in realistic experimental
environments.\end{abstract*}
\tableofcontents{}
\chapter{Introduction\label{chap:Introduction}}
Since no human being can distinguish quantities differing only by
an arbitrarily small extent \cite{Turing_1937,Gisin2017}, we want
to incorporate this limitation into our quantum mechanical model to
better capture our ability to predict quantum phenomena and the power
of realistic quantum computers. Since we are agnostic about whether
the reality is ultimately discrete or continuous, we consider two
types of quantum models. By assuming the quantum states are ultimately
discrete and distinguishable, our first type of quantum theories replaces
the complex numbers by finite fields. We then focus on the limitation
of distinguishability itself, incorporate finite precision measurements
into our model, and consider quantum interval-valued probability measures.
After first suggested by Richard Feynman 40 years ago~\cite{Feynman1982Simulating},
IBM, \textitalian{Rigetti}, Google, Microsoft, and many other companies
and countries have started to build realistic quantum computers recently
\cite{Shieber2018,Kahn2019} seeking more efficient ways to simulate
chemical molecules and breaking RSA \cite{boneh1999twenty,wiki:RSAFactoring}.
No matter how to, classical or quantum, attack these two tasks, they
require two different types of quantities. On one hand, a question
and its answer of RSA are both discrete integers. On the other hand,
molecules are described by quantities including the domain of their
position wave functions and the probability amplitudes of these wave
functions, which look like continuous at first sight. However, either
these quantities might later be discovered to be discrete, or their
exact values may never be pinned down. Hence, modeling quantum computing
based on the exact values of continuous quantities cannot really describe
the computational power of a realistic quantum computer. To better
understand this issue without struggling with the quantum theory,
it is instructive to review how classical quantities are characterized
and computed.
Discrete quantities can be easily characterized by integers~\cite{ParkerBaldridge2004}.
Even if the proportion of integers are fractions, the operations among
fractions are essentially the same as those among integers over the
common denominator. In general, discrete computation can be reliably
repeated with exact equivalence, and any digital computer can faithfully
simulate a Turing machine limited only by the available memory and
time~\cite{Turing_1937}.
In contrast, the non-apparently discrete quantities confused many
cultures since the very beginning. For example, the ancient Chinese
philosopher Chuang-tzu (庄子) didn't believe these quantities have a
minimum unit and expressed ``If a one-foot-long stick is cut into
halves every day, the cutting will never come to an end''.\footnote{``一尺之棰，日取其半，萬世不竭。'' in Chinese \cite{Zhuangzi1999,Liu2018}.}
As another example, Greek mathematicians in the school of Pythagoras
believed every mathematical model must be ultimately discrete, and
they in legend murdered Hippasus because he proved there is no minimum
unit between a side of a square and its diagonal. Comparing the idea
that the length of a square's diagonal is not a physical quantity
or there is no square physically, working with a mathematical model
without minimum unit seems more appealing. Since the mathematical
models are continuous, their corresponding physical quantities are
naturally assumed to be continuous. Later, these continuous quantities
became the basic component of analog computers. After logarithms were
discovered, a slide rule, also known as a slipstick, was used to compute
multiplication, division, and more complex operations as a mechanical
analog computer~\cite{wiki:SlideRule}. Charge amplifiers are used
to build electrical analog computers and compute integration in calculus
\cite{wiki:Integrator,wiki:ChargeAmplifier}.
Although it is convenient to assume physical quantities are as continuous
as their mathematical models, each physical quantity discussed in
the previous paragraph could not have a simple one-to-one correspondence
with a real number. Chuang-tzu's stick is made by molecules and cannot
be cut in halves endlessly. The input charge of an integrator must
be an integer multiple of the elementary charge. A perfect square
cannot be drawn physically. Even we don't draw it, but merely ask
whether it exists in the space. This question is still beyond our
ability to answer because whether space itself is ultimately discrete
or continuous is still an unsolved question. Even if a perfect square
exists physically, we may not able to decide whether the ``square''
we discussed is really perfect or almost perfect differing only by
an arbitrarily small extent. Similar situation applying to the length
of a slide rule, it is beyond our ability to decide whether its length
is ultimately discrete or continuous. Even if its length is continuous,
identifying which real number represents its length requires infinite
precision, but the precision in reality is limited generally to three
or four significant figures~\cite{wiki:AnalogComputer}. As the results,
even if analog computers really store real numbers, they cannot be
precisely read, written, and used to branch the computation. The opposite
of the last statement is sometimes assumed by real computational models.
For example, Blum, Cucker, Shub, and Smale modeled their BCSS machine
to allow the operations of deciding whether a number is greater or
equal to zero over real numbers and whether a number is exactly zero
over complex numbers \cite{BSS1989,Ziegler2007,blum2012complexity}.
Hence, when the quantities used to branch the computation closes to
zero, the branch chosen by a BCSS machine cannot reliably predict
the branch chosen by a realistic analog computer. Since two branches
of computations may not have any relations, the follow-up computational
paths may be significantly different, and this difference is unlikely
to be compensated by error analysis techniques easily like the butterfly
effect. Therefore, we might not be able to utilize a realistic analog
computer to acquire the computational power predicted by this kind
of theoretical models.%
\begin{comment}
\todo{Maybe extended to consider probabilistic model? For BCSS machine,
maybe using the idea of BPP to define the complexity class is more
reasonable than P or NP?}
\end{comment}
\begin{sidewaystable}
\begin{doublespace}
\noindent \centering{}\caption{\label{tab:Comparison}Comparison between the classical quantities
and their mathematical models with the inspired quantum models.}
%% ERT block 1 (before LyX tabular)
\renewcommand{\tabular}{\tabularx{\linewidth}}
\renewcommand{\endtabular}{\endtabularx}
\begin{tabular}{YcYY}
\toprule
Physical quantity & Discrete & Discrete with extreme small units & Continuous, or no evidence to support they are discrete\tabularnewline
\midrule
Computational device & Digital computer & Analog computer & Analog computer\tabularnewline
\midrule
\midrule
Mathematical representation & Integer & Real number & Real number\tabularnewline
\midrule
Computational model & Turing machine & BCSS machine & BCSS machine\tabularnewline
\midrule
\midrule
How does the theoretical model predict the behavior of the physical
device? & Reliably & Not reliably, but after we have better technology to manipulate the
minimum units, we can more reliably predict the physical phenomenon
and their computational power by a better discrete model. & Not reliably, because precision can never be high enough, and the
difference between their computational power might not be able compensated
by error analysis techniques.\tabularnewline
\midrule
Inspired quantum model & & Quantum theories and computing over finite fields & Quantum interval-valued probability measures (QIVPM)\tabularnewline
\bottomrule
\end{tabular}% ERT block 2 (after LyX tabular)
\renewcommand{\tabular}{\ORIGtabular}
\renewcommand{\endtabular}{\ORIGendtabular}
\end{doublespace}
\end{sidewaystable}
The situations for classical quantities and the computational power
above them are summarized in Table~\ref{tab:Comparison}, and two
possibilities for classical quantities inspires two types of quantum
models. Like its classical counterparts, quantum circuit model, the
most widely used model of quantum computing, manipulates quantities
which are not discrete apparently: the probability amplitudes of quantum
states, which are assumed in the field of complex numbers in the ``conventional
quantum theory'' (CQT).\footnote{Alternative terminology in the literature includes ``actual,'' ``standard,''
and ``ordinary'' quantum theory.} If the probability amplitudes are assumed to be ultimately discrete,
we choose to replace the field of complex numbers by discrete finite
fields for two reasons. On one hand, CQT is built upon the operations
among the probability amplitudes, and the probability amplitudes have
the required operations since the complex numbers form a field. On
the other hand, based on finite fields, we will define the fraction-like
cardinal probability which has extremely small units when the size
of the field is extremely large. Alternatively, even if the probability
amplitudes might never be found quantized, considering the precision
of quantities could still result in a better model. However, comparing
to the precision of probability amplitudes, it is easier to consider
the precision of their inducing probabilities because the idea of
``imprecise probability'' is well-studied classically \cite{Shafer1976,GilboaSchmeidler1994,Marinacci1999,JamisonLodwick2004,HuberRonchetti2009,Grabisch2016}.
\begin{comment}
\todo{Make sure whether realistic quantum computers could branch
their computation based on their probability amplitudes or measured
probabilities? If they can only branch on their measured probabilities,
it will provide another reason why we want to study the precision
of the inducing probabilities\ldots{} }
\end{comment}
This idea will be extended to quantum domain as quantum interval-valued
probability measure (QIVPM).
\begin{comment}
After a review of finite fields in Section~\ref{sec:background},
we proceed with a sequence of finite-field approaches that lead more
and more closely to the properties of conventional quantum computing.
\end{comment}
\begin{comment}
An $n$-qubit pure state in the conventional quantum theory (CQT)
is represented as a vector in the $2^{n}$-dimen\-sional Hilbert
space. If we eliminate all symmetries, an irreducible state is actually
a point in the projective Hilbert space \cite{MosseriDandoloff2001,Jaeger2007}
also known as the complex projective space~$\CP{2^{n}-1}$ \cite{Hatcher2001,Bengtsson2007}.
These irreducible quantum states can also be classified as product
states and entangled states, and the latter one plays an essential
role for pure-state algorithms \cite{Mermin2007,Jaeger2007}.
Given a pure state~$\ket{\Phi}$, when we measure an observable represented
by a Hermitian matrix~$\mathbf{O}$, the measurement result is one
of the eigenvalues of $\mathbf{O}$. The probability of getting a
particular eigenvalue~$\lambda$ is $\melem{\Phi}{P}{\Phi}$, where
$P$ is the projection operator onto the eigenspace of $\lambda$.
This rule of computing the probability is called the Born rule \cite{Born1983,Mermin2007,Jaeger2007},
which is used when we want to extract information from a quantum computer.
For any mixed state~$\rho$, the generalized Born rule induces a
conventional quantum probability measure $\muB_{\rho}\colon\events\rightarrow[0,1]$,
where $\events$ is the set of all projection operators on a given
Hilbert space. Conversely, any quantum probability measure $\mu\colon\events\rightarrow[0,1]$
can be induced from a mixed state $\rho$ in the Hilbert space of
dimension $D\ge3$ according to Gleason's theorem \cite{gleason1957,Redhead1987-REDINA,peres1995quantum,RichmanBridges1999,Hamhalter2013}.
In other words, this state $\rho$ is the unique state consistent
with any given quantum probability measure.
\end{comment}
The geometrical structure of states in CQT is first reviewed in Sec.~\ref{CQC1qubitBloch.sec},
where a pure state is represented as a vector in a Hilbert space,
and an irreducible state is actually a point in a projective Hilbert
space \cite{MosseriDandoloff2001,Jaeger2007} also known as a complex
projective space \cite{Hatcher2001,Bengtsson2007}. In Sec.~\ref{sec:fuzzy},
we will construct a quantum probability space based on classical probability
spaces, apply Gleason's theorem \cite{gleason1957,Redhead1987-REDINA,peres1995quantum,RichmanBridges1999,Hamhalter2013}
to recover the Born rule \cite{Born1983,Mermin2007,Jaeger2007}, and
define the expectation value of an observable. The expectation value
will then be used in Sec.~\ref{sec:The-geometry-of} to define purity
which provides an easy entanglement test.
\begin{comment}
In Section~\ref{modalquantum}, we examine previously-introduced
quantum theories defined over unrestricted finite fields and show
in Section~\ref{modalquantumcomputing} that this approach leads
to theories with such bizarre powers that they are probably nonphysical.
Although a version of quantum theory defined over a two-valued field
can express simple algorithms such as quantum teleportation, it is
so weak that it cannot express Deutsch's algorithm. This quantum theory
is, however, also so powerful that it can be used to solve an unstructured
database search of size $N$ using $O(\log(N))$ steps, which outperforms
the known asymptotic bound $O(\sqrt{N})$ in conventional quantum
computing.
\end{comment}
\begin{comment}
Our first discrete model replaces the complex numbers with an unrestricted
finite field~$\mathbb{F}_{q}$ \cite{Schumacher2012-SCHMQT,DQT2014,SchumacherWestmoreland2010}.
In this model, an $n$-qubit state is a non-zero vector in $\mathbb{F}_{q}^{2^{n}}$.
When we measure a given state~$\ket{\Phi}$, an observable is replaced
by a basis~$\mathcal{B}$ of $\mathbb{F}_{q}^{2^{n}}$. Since $\ket{\Phi}$
can be represented by the summation across a unique subset~$\mathcal{S}$
of the basis~$\mathcal{B}$, whether it is possible or impossible
to measure a basis vector~$\ket{i}$ depends on whether $\ket{i}$
is in $\mathcal{S}$ or not. Because this model only predicts whether
a result is possible or impossible, it is called the modal quantum
theory. Its computational model, called the modal quantum computing,
is far from conventional quantum computing. Although modal quantum
computing can express simple algorithms such as quantum teleportation
\cite{BennettBrassardEtAl1993,peres1995quantum,Mermin2007,Jaeger2007},
it is so weak that it cannot express Deutsch's algorithm \cite{Deutsch1985,Mermin2007}.
This quantum theory is, however, also so powerful that it can be used
to solve an unstructured database search of size $N$ using $O(\log(N))$
steps, which outperforms the known asymptotic bound $O(\sqrt{N})$
in conventional quantum computing \cite{Grover:1996:FQM:237814.237866,BennettBernsteinBrassardVazirani1997,Mermin2007,Jaeger2007}.
\end{comment}
In Chapter~\ref{chap:Unrestricted-Finite-Fields}, we examine previously-introduced
quantum theories defined over unrestricted finite fields \cite{Schumacher2012-SCHMQT,DQT2014,SchumacherWestmoreland2010}.
It is called the modal quantum theory because it can only predict
whether a measurement result is possible or impossible, but not its
probability. Although a version of quantum theory defined over the
two-valued field can express simple algorithms such as quantum teleportation
\cite{BennettBrassardEtAl1993,peres1995quantum,Mermin2007,Jaeger2007,Schumacher2012-SCHMQT},
it is so weak that it cannot express Deutsch's algorithm \cite{Deutsch1985,Mermin2007,DQT2014}.
This quantum theory is, however, also so powerful that it can be used
to efficiently solve the $\usat$ problem~\cite{Papadimitriou1993},
which is as hard as a general $\NP$-complete problem~\cite{Valiant198685}.
\begin{comment}
Next, in Section \ref{discretequantumtheoryI}, we improve on this
by showing that for finite fields of order $p^{2}$, with the prime
$p$ of the form $4\ell+3$ ($\ell$ a non-negative integer), the
complex numbers have extremely compelling and natural discrete analogs
that permit a great many of the standard requirements of quantum computing
to be preserved. Under suitable conditions, we have amplitude-based
partitions of unity, unitary transformations, and entanglement, as
well as solutions to deterministic quantum algorithms such as the
algorithms of Deutsch, Simon, and Bernstein-Vazirani~\cite{NCbook,Mermin},
though still with some bothersome shortcomings. Because of the modular
nature of arithmetic in the finite complex field, it is not possible
to define an inner product in the usual sense, and we show in Section~\ref{discretequantumcomputingI}
that this leads to excessive computational power for the unstructured
database search problem for certain database sizes.
\end{comment}
\begin{comment}
Our second model called discrete quantum theory (I) considers only
finite fields of order $p^{2}$, with the prime $p$ of the form $4\ell+3$
($\ell$ a non-negative integer) \cite{geometry2013,DQT2014}. In
this model, an irreducible state is a vector in $\mathbb{F}_{p^{2}}^{2^{n}}$,
and can be reduced to a point in the discrete complex projective space~$\mathbb{DCP}^{2^{n}-1}$.
Among these irreducible states, the product states and entangled states
can not only be identified as in CQT but also be counted for different
$p$. Although the state space is a natural discrete analog to CQT,
this model still only predicts whether a measurement result is possible
or impossible, because it is not possible to define an inner product
in the usual sense due to the modular arithmetic~\cite{grove2002classical}.
Under suitable conditions, we can have deterministic quantum algorithms
such as the algorithms of Deutsch, Simon \cite{Simon:1994:PQC:1398518.1399019,Mermin2007,Jaeger2007},
and Bernstein-Vazirani \cite{Bernstein:1993:QCT:167088.167097,Mermin2007},
but this still leads to excessive computational power for the unstructured
database search problem for certain database sizes.
\end{comment}
In Sec.~\ref{discretequantumtheoryI} to~\ref{discretequantumcomputingI},
we improve on this by showing that for finite fields of order $p^{2}$,
$\Fpp$, with the prime $p$ of the form $4\ell+3$ ($\ell$ a non-negative
integer), the complex numbers then have extremely compelling and natural
discrete analogs that preserve a great many of the standard requirements
of quantum computing. In this model, the state of a discrete $D$-dimen\-sional
system is a vector in the $D$-dimen\-sional vector space over $\Fpp$
and can be reduced to a point in the discrete complex projective space.
Among these irreducible states, the product states and entangled states
could not only be identified as in CQT but also be counted for different
$p$. Despite the similarity between this model and CQT, it still
only predicts whether a measurement result is possible or impossible
because it is not possible to define an inner product in the usual
sense due to the modular arithmetic~\cite{grove2002classical}. Under
suitable conditions, we can have deterministic quantum algorithms
such as the algorithms of Deutsch, Simon \cite{Simon:1994:PQC:1398518.1399019,Mermin2007,Jaeger2007},
and Bernstein-Vazirani \cite{Bernstein:1993:QCT:167088.167097,Mermin2007},
but this still leads to excessive computational power for partially
solving the $\usat$ problem efficiently.
\begin{comment}
We are led, in Sections~\ref{discretequantumtheoryIIa} and~\ref{discretequantumtheoryIIb},
to develop a framework with further restrictions on~$p$ that \emph{locally\/}
recovers the structure and expected properties of conventional quantum
theory. Section~\ref{discretequantumtheoryIIa} locally recovers
the inner product space and Section~\ref{discretequantumtheoryIIb}
locally recovers a notion of probability. The development in both
sections exploits the fact that longer sequences of \textit{ordered\/}
numbers appear in the quadratic residues (numbers with square-roots
in the field) as the size of the field increases. Discrete quantum
computations whose calculations are confined to numbers in this ordered
sequence resemble conventional quantum computations. The size of the
field $p$ plays an important role in describing the resources needed
for the computation as larger problem sizes require a larger field
size to represent all intermediate numerical values. A significant
feature of our framework is that the resources needed for the measurement
process can be separated from the resources needed by the evolution
of the system being modeled. This interplay between the resources
used by the system under study and the resources used for the observation
process is a significant concept that is nonexistent in conventional
quantum computing and is exposed by our careful accounting of resources.
We note that the conventional mathematical framework based on the
real numbers allows one to distinguish states whose measurement outcomes
differ by infinitesimally small probabilities, e.g., $10^{-100}$
vs.~$0$. In the proposed framework of discrete quantum computing,
the finite size of the field implies a maximum precision for measurement:
a ``small'' field represents limited resources with which it becomes
impossible to distinguish states whose measurement outcomes differ
by an amount less than the resolution afforded by the field. It is
possible, however, to discriminate between such states at the cost
of moving to a larger field, i.e., by investing more resources in
the measurement process. We formalize this approach to measurement
using the novel notion of \textit{cardinal probability\/}, with numerical
labels corresponding to ``more probable, the same, or less probable,''
rather than a percentage-based likelihood measure. In cardinal probability,
relative outcomes are associated with intervals of ambiguity that
get smaller and more precise as the size of the field increases.
Finally, in Section~\ref{discretequantumcomputingII}, we apply our
discrete quantum theory to the study of two representative algorithms,
the deterministic Deutsch-Jozsa algorithm and the probabilistic Grover
algorithm~\cite{NCbook,Mermin}. The first algorithm highlights the
role played by the size of the field $p$ in determining the actual
resources required for computation as the number of input bits $n$
increases, a concept nonexistent in conventional quantum computing.
The second algorithm highlights, in addition, the dependence of the
precision of measurement (via cardinal probabilities) on the size
of the field, another nonexistent concept in conventional quantum
computing.
\end{comment}
\begin{comment}
Our third model, discrete quantum theory (II)~\cite{DQT2014}, restricts
states in some local region of $\mathbb{F}_{p^{2}}^{2^{n}}$. Within
a local region, a notion of inner product and probability could be
recovered. Its discrete quantum computing can be further applied to
the deterministic Deutsch-Jozsa algorithm \cite{DeutschJozsa1992,Jaeger2007}
and the probabilistic Grover algorithm \cite{Grover:1996:FQM:237814.237866,Mermin2007,Jaeger2007}.
\end{comment}
Since many important quantum algorithms are probabilistic, we want
to find a notion of probability for quantum theories over finite fields.
The cardinal probability defined in Sec.~\ref{sec:Discrete-Quantum-Theory-(II)}
restricts states in some local regions of the vector spaces, where
a notion of inner product and probability could be recovered. In Sec.~\ref{discretequantumcomputingII},
this discrete quantum theory is applied to two representative algorithms,
the deterministic Deutsch-Jozsa algorithm \cite{DeutschJozsa1992,Jaeger2007}
and the probabilistic Grover algorithm \cite{Grover:1996:FQM:237814.237866,Mermin2007,Jaeger2007}.
\begin{comment}
When people tried to define quantum probability over finite fields,
people tended to treat the original Born rule as an axiom and tried
to modify it to get a discrete Born rule \cite{Schumacher2012-SCHMQT,doi:10.1142/S0217984913500644,DQT2014,Ellerman2016a}.
However, any modified Born rule could hardly work on the whole vector
space, since there is no inner product on the whole vector space over
finite fields. Instead of treating the Born rule as an axiom, the
Born rule can be deduced from a set of abstract definitions and axioms
according to Gleason's theorem. Although we might hope to deduce a
discrete Born rule directly from a similar set of definitions and
axioms, no discrete Born rule satisfies certain properties motivated
by Gleason's theorem with infinitely precise real-number probability~\cite{Gardiner2014}.
Since the state spaces are now discrete and finite, this suggests
us to consider a discrete Born rule mapping to a finite number of
intervals called interval-valued probability~\cite{JamisonLodwick2004,THOS2017}.
To adopting the idea of interval-valued probability step-by-step,
before attempting to study quantum interval-valued probability over
finite fields, we will first review the classical interval-valued
probability and extend it with the conventional quantum theory.
\end{comment}
Despite the great success of cardinal probabilities, it is difficult
to define their arithmetic operations and expectation values. Since
they could be defined easily with real-valued probabilities in CQT,
we attempt to consider real-valued quantum probability measures over
finite fields (QPMFF) in Sec.~\ref{sec:Toward-IVPM}. In contrast
to CQT, our Gleason-like conditions over finite fields cannot deduce
a discrete Born rule in general. This impossible result suggests that
the discrete and finite state spaces might not be compatible with
infinitely precise real-valued probability. Thus, no matter whether
the probability amplitudes are ultimately discrete or continuous,
we should study imprecise quantum probabilities formulated by quantum
interval-valued probability measures.
\begin{comment}
In the classical setting, there are several proposals for ``imprecise
probabilities'' \cite{Shafer1976,GilboaSchmeidler1994,Marinacci1999,JamisonLodwick2004,HuberRonchetti2009,Grabisch2016}.
Although these proposals differ in some details, they all share the
fact that the probability $\bar{\mu}(E)$ of an event~$E$ is generalized
from a single \emph{real number} to an \emph{interval}~$[l,r]$,
where~$l$ intuitively corresponds to the strength of evidence for
the event~$E$ and~$1-r$ corresponds to the strength of the evidence
against the same event. Given a sample space~$\Omega$ and a set
of intervals~$\mathscr{I}$, like a classical probability measure
$\mu\colon2^{\Omega}\rightarrow\left[0,1\right]$, a classical interval-valued
probability measure (IVPM) $\bar{\mu}\colon2^{\Omega}\rightarrow\mathscr{I}$
needs to satisfy some coherent axioms. By satisfying the convexity
axiom \cite{Shapley1971,GilboaSchmeidler1994,Marinacci1999,Grabisch2016},
Shapley proved that there is always a classical probability measure
consistent with the classical IVPM~$\bar{\mu}$ \cite{Shapley1971,GilboaSchmeidler1994,Grabisch2016}.
Given any random variable, its expectation value with respect to classical
probability measures consistent with~$\bar{\mu}$ is consistent with
its Choquet integral \cite{Choquet1954,GilboaSchmeidler1994,Grabisch2016}
with respect to $\bar{\mu}$ \cite{Rosenmuller1971,GilboaSchmeidler1994,Grabisch2016}.
The quantum extension, quantum interval-valued probability measure
(QIVPM) $\bar{\mu}\colon\events\rightarrow\mathscr{I}$, is a generalization
of both classical IVPMs $\bar{\mu}\colon2^{\Omega}\rightarrow\mathscr{I}$
and conventional quantum probability measures $\mu\colon\events\rightarrow[0,1]$
\cite{THOS2017}, because QIVPMs reduce to classical IVPMs when the
space of quantum events $\events$ is restricted to mutually commuting
events and reduce to conventional quantum probability measures when
mapping to infinitely precise uncountable intervals $\mathscr{I}_{\infty}=\set{\left[x,x\right]}{x\in\left[0,1\right]}$.
While Shapley and Gleason both proved there must be a ``state''
consistent with any given QIVPM in the reduced cases, in general,
there exists a QIVPM such that no state is consistent with it. However,
we found a class of QIVPMs such that all QIVPMs in this class are
consistent with a non-empty ``ball'' of quantum states whose radius
is defined by the maximal length of the intervals and recovers the
original Gleason theorem asymptotically. Similarly, the conventional
quantum expectation value and the classical Choquet integral are together
generalized to the quantum interval-valued expectation value. This
is used to prove an imprecise Kochen-Specker theorem \cite{BELL_1966,kochenspecker1967,Redhead1987-REDINA,peres1995quantum,Jaeger2007}
which suggests a possible resolution of the Meyer-Mermin debate on
the impact of finite-precision measurement on the Kochen-Specker theorem
\cite{PhysRevLett.83.3751,Mermin1999}.
\end{comment}
\begin{comment}
We present a mathematical framework based on quantum interval-valued
probability measures to study the effect of experimental imperfections
and finite precision measurements on defining aspects of quantum mechanics
such as contextuality and the Born rule. While foundational results
such as the Kochen-Specker and Gleason theorems are valid in the context
of infinite precision, they fail to hold in general in a world with
limited resources. Here we employ an interval-valued framework to
establish bounds on the validity of those theorems in realistic experimental
environments. In this way, not only can we quantify the idea of finite-precision
measurement within our theory, but we can also suggest a possible
resolution of the Meyer-Mermin debate on the impact of finite-precision