We study the combinatorial and algebraic properties of Nonnegative Matrices. Our results are divided into three different categories.
(1/15) • [(Δ(R))/n] ≤ φ(R) ≤ √[2 • Δ(R)].
This also provides a more general result than the Cheeger-Buser inequalities since it applies to any nonnegative matrix.
φ(R) ≤ [(Δ(R))/√n],
obtaining a bound exponentially better than known bounds. We also present a candidate construction of matrices for which
φ(R) ≤ 2[(Δ(R))/n]
which is the most beautiful contribution of this thesis. We believe these matrices have properties remarkable enough to deserve study in their own right.
3. We connect the edge expansion and spectral gap to other combinatorial properties of nonsymmetric matrices. The most well-studied property is mixing time, and we provide elementary proofs of the relation between mixing time and the edge expansion, and also other bounds relating the mixing time of a nonreversible chain to the spectral gap and to its additive symmetrization. Further, we provide a unified view of the notion of capacity and normalized capacity, and show the monotonicity of capacity of nonreversible chains amongst other results for nonsymmetric matrices. We finally discuss and prove interesting lemmas about different notions of expansion and show the first results for tensor walks or nonnegative tensors.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Schulman, Leonard J. and Vidick, Thomas G.}, } @phdthesis{10.7907/v7dm-6r52, author = {Cvitkovic, Michael William (Milan0}, title = {Deep Learning in Unconventional Domains}, school = {California Institute of Technology}, year = {2020}, doi = {10.7907/v7dm-6r52}, url = {https://resolver.caltech.edu/CaltechTHESIS:04082020-095943405}, abstract = {Machine learning methods have dramatically improved in recent years thanks to advances in deep learning (LeCun et al., 2015), a set of methods for training high-dimensional, highly-parameterized, nonlinear functions. Yet deep learning progress has been concentrated in the domains of computer vision, vision-based reinforcement learning, and natural language processing. This dissertation is an attempt to extend deep learning into domains where it has thus far had little impact or has never been applied. It presents new deep learning algorithms and state-of-the-art results on tasks in the domains of source-code analysis, relational databases, and tabular data.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Vidick, Thomas G.}, } @phdthesis{10.7907/VQC0-ZK80, author = {Coladangelo, Andrea Wei}, title = {Quantum Correlations, Certifying Quantum Devices, and the Quest for Infinite Entanglement}, school = {California Institute of Technology}, year = {2020}, doi = {10.7907/VQC0-ZK80}, url = {https://resolver.caltech.edu/CaltechTHESIS:01162020-013448014}, abstract = {Quantum information has the potential to disrupt the present computational landscape. Much of this potential rests on the existence of efficient quantum algorithms for classically intractable problems and of quantum cryptographic protocols for tasks that are provably impossible to realize classically. At the heart of many quantum advantages is one of the most counterintuitive features of quantum mechanics, known as entanglement. The central motivating question of this thesis is the following: if quantum devices will perform tasks that are beyond the reach of classical devices, can we hope to certify that they are performing these tasks correctly? Bell’s theorem, a landmark result in physics, provides a partial answer to this question: it asserts that measurements on spatially isolated, but entangled, particles can result in outcomes that are correlated in a way that cannot be explained by any local hidden variable theory (such as Newtonian physics). A direct operational consequence of this theorem is that one can devise a statistical test to certify the presence of entanglement (and hence of genuine quantumness). Remarkably, nature allows us to take this certification one step further: in some cases, the correlation of measurement outcomes is sufficient to single out a unique quantum setup compatible with this correlation. This phenomenon is often referred to as self-testing, and is the central topic of this thesis.
In the first part of this thesis, we review the basic terminology and results in the theory of self-testing. We then explore a concrete application to the problem of verifiably delegating a quantum computation. Our main technical contribution is a test that robustly certifies products of single-qubit Clifford measurements on many EPR pairs. We employ this test to obtain a protocol which allows a classical user to verifiably delegate her quantum computation to two spatially isolated quantum servers. The overall complexity of our protocol is near-optimal, requiring resources that scale almost linearly in the size of the circuit being delegated.
In the second part of this thesis, the driving question is the following: what is the class of quantum states and measurements that can be certified through self-testing? Does self-testing only apply to a few special cases, like EPR pairs or copies of EPR pairs, or are these instances of a more general phenomenon? One of the main results of this thesis is that we settle this question for the case of bipartite states. We show the existence of a self-testing correlation for any pure bipartite entangled state of any finite local dimension. We then move on to explore the multipartite case, and we show that a significantly larger class of states can be self-tested than was previously known. This includes all multipartite partially entangled GHZ states, and more generally all multipartite qudit states which admit a Schmidt decomposition.
In the final part of this thesis, we explore connections of the theory of self-testing to basic questions about entanglement and quantum correlation sets. In particular, we set out to understand the expressive power of infinite-dimensional quantum systems. We consider two questions: can spatially isolated quantum systems of infinite dimension produce correlations that are unattainable by finite-dimensional systems? Does there exist a correlation that cannot be attained exactly by spatially isolated quantum systems (not even infinite-dimensional ones), but can be approximated arbitrarily well by a sequence of finite or infinite-dimensional systems? The first question was posed by Tsirelson in 1993, and its answer has been elusive. One of the main results of this thesis is a resolution of this question. The second question is better known as the “non-closure of the set of quantum correlations”, and was answered affirmatively in a breakthrough of Slofstra. We give a new elementary proof of this result which leverages one of our self-testing results and a phenomenon known as embezzlement.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Vidick, Thomas G.}, } @mastersthesis{10.7907/Z9V98611, author = {Mehta, Jenish C.}, title = {Behavior of O(log n) Local Commuting Hamiltonians}, school = {California Institute of Technology}, year = {2016}, doi = {10.7907/Z9V98611}, url = {https://resolver.caltech.edu/CaltechTHESIS:05272016-141059835}, abstract = {
We study the variant of the k-local hamiltonian problem which is a natural generalization of k-CSPs, in which the hamiltonian terms all commute. More specifically, we consider a hamiltonian H over n qubits, where H is a sum of k-local terms acting non-trivially on O(log n) qubits, and all the k-local terms commute, and show the following -
The first two behaviours seem to indicate that deciding whether the ground space energy of O(log n)-local commuting hamiltonians is low or high might be in NP or possibly QCMA, though the last behaviour seems to indicate that it may indeed be the case that O(log n)-local commuting hamiltonians are QMA complete.
}, address = {1200 East California Boulevard, Pasadena, California 91125}, advisor = {Vidick, Thomas G. and Schulman, Leonard J.}, }