Researcher profile

Tobias Fritz

Tobias Fritz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
21topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2022arXiv

Non-abelian and $\varepsilon$-curved homological algebra with arrow categories

Grandis's non-abelian homological algebra generalizes standard homological algebra in abelian categories to \textit{homological categories}, which are a broader class of categories including for example the category of lattices and Galois connections. Here, we prove that if $\mathsf{C}$ is any category with an ideal of null morphisms with respect to which (co)kernels exist, then the arrow category of $\mathsf{C}$ is a homological category. This broadens the applicability of Grandis's framework substantially. In particular, one can form the homology of chain complexes in $\mathsf{C}$ by taking the homology objects to be morphisms of $\mathsf{C}$, which one may think of as maps from an object of cycles to an object of chains modulo boundaries. One situation to which Grandis's original framework does not apply is \textit{$\varepsilon$-curved homological algebra}. This refers to chain complexes of normed spaces whose differential squares to zero only approximately, in the sense that $\|d^2\| \leq \varepsilon$ for some $\varepsilon > 0$. This is relevant for example in the theory of approximate representations of groups, where Kazhdan has successfully employed $\varepsilon$-curved homological techniques in an ad-hoc manner. We develop some basics of $\varepsilon$-curved homological algebra and note that our result on arrow categories facilitates the application of Grandis's theory.

preprint2021arXiv

Probability, valuations, hyperspace: Three monads on Top and the support as a morphism

We consider three monads on Top, the category of topological spaces, which formalize topological aspects of probability and possibility in categorical terms. The first one is the Hoare hyperspace monad H, which assigns to every space its space of closed subsets equipped with the lower Vietoris topology. The second is the monad V of continuous valuations, also known as the extended probabilistic powerdomain. We construct both monads in a unified way in terms of double dualization. This reveals a close analogy between them, and allows us to prove that the operation of taking the support of a continuous valuation is a morphism of monads from V to H. In particular, this implies that every H-algebra (topological complete semilattice) is also a V-algebra. Third, we show that V can be restricted to a submonad of tau-smooth probability measures on Top. By composing these two morphisms of monads, we obtain that taking the support of a tau-smooth probability measure is also a morphism of monads.

preprint2020arXiv

A generalization of Strassen's Positivstellensatz

Strassen's Positivstellensatz is a powerful but little known theorem on preordered commutative semirings satisfying a boundedness condition similar to Archimedeanicity. It characterizes the relaxed preorder induced by all monotone homomorphisms to $\mathbb{R}_+$ in terms of a condition involving large powers. Here, we generalize and strengthen Strassen's result. As a generalization, we replace the boundedness condition by a polynomial growth condition; as a strengthening, we prove two further equivalent characterizations of the homomorphism-induced preorder in our generalized setting.

preprint2020arXiv

A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics

We develop Markov categories as a framework for synthetic probability and statistics, following work of Golubtsov as well as Cho and Jacobs. This means that we treat the following concepts in purely abstract categorical terms: conditioning and disintegration; various versions of conditional independence and its standard properties; conditional products; almost surely; sufficient statistics; versions of theorems on sufficient statistics due to Fisher--Neyman, Basu, and Bahadur. Besides the conceptual clarity offered by our categorical setup, its main advantage is that it provides a uniform treatment of various types of probability theory, including discrete probability theory, measure-theoretic probability with general measurable spaces, Gaussian probability, stochastic processes of either of these kinds, and many others.

preprint2020arXiv

Bimonoidal Structure of Probability Monads

We give a conceptual treatment of the notion of joints, marginals, and independence in the setting of categorical probability. This is achieved by endowing the usual probability monads (like the Giry monad) with a monoidal and an opmonoidal structure, mutually compatible (i.e. a bimonoidal structure). If the underlying monoidal category is cartesian monoidal, a bimonoidal structure is given uniquely by a commutative strength. However, if the underlying monoidal category is not cartesian monoidal, a strength is not enough to guarantee all the desired properties of joints and marginals. A bimonoidal structure is then the correct requirement for the more general case. We explain the theory and the operational interpretation, with the help of the graphical calculus for monoidal categories. We give a definition of stochastic independence based on the bimonoidal structure, compatible with the intuition and with other approaches in the literature for cartesian monoidal categories. We then show as an example that the Kantorovich monad on the category of complete metric spaces is a bimonoidal monad for a non-cartesian monoidal structure.

preprint2020arXiv

Optimal bounds on the positivity of a matrix from a few moments

In many contexts one encounters Hermitian operators $M$ on a Hilbert space whose dimension is so large that it is impossible to write down all matrix entries in an orthonormal basis. How does one determine whether such $M$ is positive semidefinite? Here we approach this problem by deriving asymptotically optimal bounds to the distance to the positive semidefinite cone in Schatten $p$-norm for all integer $p\in[1,\infty)$, assuming that we know the moments $\mathbf{tr}(M^k)$ up to a certain order $k=1,\ldots, m$. We then provide three methods to compute these bounds and relaxations thereof: the sos polynomial method (a semidefinite program), the Handelman method (a linear program relaxation), and the Chebyshev method (a relaxation not involving any optimization). We investigate the analytical and numerical performance of these methods and present a number of example computations, partly motivated by applications to tensor networks and to the theory of free spectrahedra.

preprint2020arXiv

Stochastic order on metric spaces and the ordered Kantorovich monad

In earlier work, we had introduced the Kantorovich probability monad on complete metric spaces, extending a construction due to van Breugel. Here we extend the Kantorovich monad further to a certain class of ordered metric spaces, by endowing the spaces of probability measures with the usual stochastic order. It can be considered a metric analogue of the probabilistic powerdomain. The spaces we consider, which we call L-ordered, are spaces where the order satisfies a mild compatibility condition with the metric itself, rather than merely with the underlying topology. As we show, this is related to the theory of Lawvere metric spaces, in which the partial order structure is induced by the zero distances. We show that the algebras of the ordered Kantorovich monad are the closed convex subsets of Banach spaces equipped with a closed positive cone, with algebra morphisms given by the short and monotone affine maps. Considering the category of L-ordered metric spaces as a locally posetal 2-category, the lax and oplax algebra morphisms are exactly the concave and convex short maps, respectively. In the unordered case, we had identified the Wasserstein space as the colimit of the spaces of empirical distributions of finite sequences. We prove that this extends to the ordered setting as well by showing that the stochastic order arises by completing the order between the finite sequences, generalizing a recent result of Lawson. The proof holds on any metric space equipped with a closed partial order.

preprint2019arXiv

Curious properties of free hypergraph C*-algebras

A finite hypergraph $H$ consists of a finite set of vertices $V(H)$ and a collection of subsets $E(H) \subseteq 2^{V(H)}$ which we consider as partition of unity relations between projection operators. These partition of unity relations freely generate a universal C*-algebra, which we call the "free hypergraph C*-algebra" $C^*(H)$. General free hypergraph C*-algebras were first studied in the context of quantum contextuality. As special cases, the class of free hypergraph C*-algebras comprises quantum permutation groups, maximal group C*-algebras of graph products of finite cyclic groups, and the C*-algebras associated to quantum graph homomorphism, isomorphism, and colouring. Here, we conduct the first systematic study of aspects of free hypergraph C*-algebras. We show that they coincide with the class of finite colimits of finite-dimensional commutative C*-algebras, and also with the class of C*-algebras associated to synchronous nonlocal games. We had previously shown that it is undecidable to determine whether $C^*(H)$ is nonzero for given $H$. We now show that it is also undecidable to determine whether a given $C^*(H)$ is residually finite-dimensional, and similarly whether it only has infinite-dimensional representations, and whether it has a tracial state. It follows that for each one of these properties, there is $H$ such that the question whether $C^*(H)$ has this property is independent of the ZFC axioms, assuming that these are consistent. We clarify some of the subtleties associated with such independence results in an appendix.

preprint2019arXiv

The universal property of infinite direct sums in C$^*$-categories and W$^*$-categories

When formulating universal properties for objects in a dagger category, one usually expects a universal property to characterize the universal object up to unique unitary isomorphism. We observe that this is automatically the case in the important special case of C$^*$-categories, provided that one uses enrichment in Banach spaces. We then formulate such a universal property for infinite direct sums in C$^*$-categories, and prove the equivalence with the existing definition due to Ghez, Lima and Roberts in the case of W$^*$-categories. These infinite direct sums specialize to the usual ones in the category of Hilbert spaces, and more generally in any W$^*$-category of normal representations of a W$^*$-algebra. Finding a universal property for the more general case of direct integrals remains an open problem.

preprint2013arXiv

On infinite-dimensional state spaces

It is well-known that the canonical commutation relation $[x,p]=i$ can be realized only on an infinite-dimensional Hilbert space. While any finite set of experimental data can also be explained in terms of a finite-dimensional Hilbert space by approximating the commutation relation, Occam's razor prefers the infinite-dimensional model in which $[x,p]=i$ holds on the nose. This reasoning one will necessarily have to make in any approach which tries to detect the infinite-dimensionality. One drawback of using the canonical commutation relation for this purpose is that it has unclear operational meaning. Here, we identify an operationally well-defined context from which an analogous conclusion can be drawn: if two unitary transformations $U,V$ on a quantum system satisfy the relation $V^{-1}U^2V=U^3$, then finite-dimensionality entails the relation $UV^{-1}UV=V^{-1}UVU$; this implication strongly fails in some infinite-dimensional realizations. This is a result from combinatorial group theory for which we give a new proof. This proof adapts to the consideration of cases where the assumed relation $V^{-1}U^2V=U^3$ holds only up to $\eps$ and then yields a lower bound on the dimension.

preprint2013arXiv

Velocity Polytopes of Periodic Graphs and a No-Go Theorem for Digital Physics

A periodic graph in dimension $d$ is a directed graph with a free action of $\Z^d$ with only finitely many orbits. It can conveniently be represented in terms of an associated finite graph with weights in $\Z^d$, corresponding to a $\Z^d$-bundle with connection. Here we use the weight sums along cycles in this associated graph to construct a certain polytope in $\R^d$, which we regard as a geometrical invariant associated to the periodic graph. It is the unit ball of a norm on $\R^d$ describing the large-scale geometry of the graph. It has a physical interpretation as the set of attainable velocities of a particle on the graph which can hop along one edge per timestep. Since a polytope necessarily has distinguished directions, there is no periodic graph for which this velocity set is isotropic. In the context of classical physics, this can be viewed as a no-go theorem for the emergence of an isotropic space from a discrete structure.

preprint2012arXiv

An entropic approach to local realism and noncontextuality

For any Bell locality scenario (or Kochen-Specker noncontextuality scenario), the joint Shannon entropies of local (or noncontextual) models define a convex cone for which the non-trivial facets are tight entropic Bell (or contextuality) inequalities. In this paper we explore this entropic approach and derive tight entropic inequalities for various scenarios. One advantage of entropic inequalities is that they easily adapt to situations like bilocality scenarios, which have additional independence requirements that are non-linear on the level of probabilities, but linear on the level of entropies. Another advantage is that, despite the nonlinearity, taking detection inefficiencies into account turns out to be very simple. When joint measurements are conducted by a single detector only, the detector efficiency for witnessing quantum contextuality can be arbitrarily low.

preprint2012arXiv

Beyond Bell's Theorem: Correlation Scenarios

Bell's Theorem witnesses that the predictions of quantum theory cannot be reproduced by theories of local hidden variables in which observers can choose their measurements independently of the source. Working out an idea of Branciard, Rosset, Gisin and Pironio, we consider scenarios which feature several sources, but no choice of measurement for the observers. Every Bell scenario can be mapped into such a \emph{correlation scenario}, and Bell's Theorem then discards those local hidden variable theories in which the sources are independent. However, most correlation scenarios do not arise from Bell scenarios, and we describe examples of (quantum) nonlocality in some of these scenarios, while posing many open problems along the way. Some of our scenarios have been considered before by mathematicians in the context of causal inference.

preprint2012arXiv

Entropic Inequalities and Marginal Problems

A marginal problem asks whether a given family of marginal distributions for some set of random variables arises from some joint distribution of these variables. Here we point out that the existence of such a joint distribution imposes non-trivial conditions already on the level of Shannon entropies of the given marginals. These entropic inequalities are necessary (but not sufficient) criteria for the existence of a joint distribution. For every marginal problem, a list of such Shannon-type entropic inequalities can be calculated by Fourier-Motzkin elimination, and we offer a software interface to a Fourier-Motzkin solver for doing so. For the case that the hypergraph of given marginals is a cycle graph, we provide a complete analytic solution to the problem of classifying all relevant entropic inequalities, and use this result to bound the decay of correlations in stochastic processes. Furthermore, we show that Shannon-type inequalities for differential entropies are not relevant for continuous-variable marginal problems; non-Shannon-type inequalities are, both in the discrete and in the continuous case. In contrast to other approaches, our general framework easily adapts to situations where one has additional (conditional) independence requirements on the joint distribution, as in the case of graphical models. We end with a list of open problems. A complementary article discusses applications to quantum nonlocality and contextuality.

preprint2012arXiv

Nonlocality with less Complementarity

In quantum mechanics, nonlocality (a violation of a Bell inequality) is intimately linked to complementarity, by which we mean that consistently assigning values to different observables at the same time is not possible. Nonlocality can only occur when some of the relevant observables do not commute, and this noncommutativity makes the observables complementary. Beyond quantum mechanics, the concept of complementarity can be formalized in several distinct ways. Here we describe some of these possible formalizations and ask how they relate to nonlocality. We partially answer this question by describing two toy theories which display nonlocality and obey the no-signaling principle, although each of them does not display a certain kind of complementarity. The first toy theory has the property that it maximally violates the CHSH inequality, although the corresponding local observables are pairwise jointly measurable. The second toy theory also maximally violates the CHSH inequality, although its state space is classical and all measurements are mutually nondisturbing: if a measurement sequence contains some measurement twice with any number of other measurements in between, then these two measurements give the same outcome with certainty.

preprint2012arXiv

Polyhedral duality in Bell scenarios with two binary observables

For the Bell scenario with two parties and two binary observables per party, it is known that the no-signaling polytope is the polyhedral dual (polar) of the Bell polytope. Computational evidence suggests that this duality also holds for three parties. Using ideas of Werner, Wolf, Żukowski and Brukner, we prove this for any number of parties by describing a simple linear bijection mapping (tight) Bell inequalities to (extremal) no-signaling boxes and vice versa. Furthermore, a symmetry-based technique for extending Bell inequalities (resp. no-signaling boxes) with two binary observables from n parties to n+1 parties is described; the Mermin-Klyshko family of Bell inequalities arises in this way, as well as 11 of the 46 classes of tight Bell inequalities for 3 parties. Finally, we ask whether the set of quantum correlations is self-dual with respect to our transformation. We find this not to be the case in general, although it holds for 2 parties on the level of correlations. This self-duality implies Tsirelson's bound for the CHSH inequality.

preprint2012arXiv

Tsirelson's problem and Kirchberg's conjecture

Tsirelson's problem asks whether the set of nonlocal quantum correlations with a tensor product structure for the Hilbert space coincides with the one where only commutativity between observables located at different sites is assumed. Here it is shown that Kirchberg's QWEP conjecture on tensor products of C*-algebras would imply a positive answer to this question for all bipartite scenarios. This remains true also if one considers not only spatial correlations, but also spatiotemporal correlations, where each party is allowed to apply their measurements in temporal succession; we provide an example of a state together with observables such that ordinary spatial correlations are local, while the spatiotemporal correlations reveal nonlocality. Moreover, we find an extended version of Tsirelson's problem which, for each nontrivial Bell scenario, is equivalent to the QWEP conjecture. This extended version can be conveniently formulated in terms of steering the system of a third party. Finally, a comprehensive mathematical appendix offers background material on complete positivity, tensor products of C*-algebras, group C*-algebras, and some simple reformulations of the QWEP conjecture.

preprint2011arXiv

Hardy's Non-locality Paradox and Possibilistic Conditions for Non-locality

Hardy's non-locality paradox is a proof without inequalities showing that certain non-local correlations violate local realism. It is `possibilistic' in the sense that one only distinguishes between possible outcomes (positive probability) and impossible outcomes (zero probability). Here we show that Hardy's paradox is quite universal: in any (2,2,l) or (2,k,2) Bell scenario, the occurence of Hardy's paradox is a necessary and sufficient condition for possibilistic non-locality. In particular, it subsumes all ladder paradoxes. This universality of Hardy's paradox is not true more generally: we find a new `proof without inequalities' in the (2,3,3) scenario that can witness non-locality even for correlations that do not display the Hardy paradox. We discuss the ramifications of our results for the computational complexity of recognising possibilistic non-locality.

preprint2010arXiv

On the existence of quantum representations for two dichotomic measurements

Under which conditions do outcome probabilities of measurements possess a quantum-mechanical model? This kind of problem is solved here for the case of two dichotomic von Neumann measurements which can be applied repeatedly to a quantum system with trivial dynamics. The solution uses methods from the theory of operator algebras and the theory of moment problems. The ensuing conditions reveal surprisingly simple relations between certain quantum-mechanical probabilities. It also shown that generally, none of these relations holds in general probabilistic models. This result might facilitate further experimental discrimination between quantum mechanics and other general probabilistic theories.

preprint2010arXiv

Transition probabilities and measurement statistics of postselected ensembles

It is well-known that a quantum measurement can enhance the transition probability between two quantum states. Such a measurement operates after preparation of the initial state and before postselecting for the final state. Here we analyze this kind of scenario in detail and determine which probability distributions on a finite number of outcomes can occur for an intermediate measurement with postselection, for given values of the following two quantities: (i) the transition probability without measurement, (ii) the transition probability with measurement. This is done for both the cases of projective measurements and of generalized measurements. Among other constraints, this quantifies a trade-off between high randomness in a projective measurement and high measurement-modified transition probability. An intermediate projective measurement can enhance a transition probability such that the failure probability decreases by a factor of up to 2, but not by more.