Source author record

Jamie Pommersheim

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.AG math.CO math.MG quant-ph

Catalog footprint

Research overview

3works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Quantum query complexity of symmetric oracle problems

We study the query complexity of quantum learning problems in which the oracles form a group $G$ of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a $t$ -query quantum algorithm in terms of group characters. As an application, we show that $Ω(n)$ queries are required to identify a random permutation in $S_n$ . More generally, suppose $H$ is a fixed subgroup of the group $G$ of oracles, and given access to an oracle sampled uniformly from $G$ , we want to learn which coset of $H$ the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a $t$ -query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on $n$ which require $n+1$ queries classically and only $1$ query quantumly.

preprint2020arXiv

Generalized Dissections and Monsky's Theorem

Monsky's celebrated equidissection theorem follows from his more general proof of the existence of a polynomial relation $f$ among the areas of the triangles in a dissection of the unit square. More recently, the authors studied a different polynomial $p$ , also a relation among the areas of the triangles in such a dissection, that is invariant under certain deformations of the dissection. In this paper we study the relationship between these two polynomials. We first generalize the notion of dissection, allowing triangles whose orientation differs from that of the plane. We define a deformation space of these generalized dissections and we show that this space is an irreducible algebraic variety. We then extend the theorem of Monsky to the context of generalized dissections, showing that Monsky's polynomial $f$ can be chosen to be invariant under deformation. Although $f$ is not uniquely defined, the interplay between $p$ and $f$ then allows us to identify a canonical pair of choices for the polynomial $f$ . In many cases, all of the coefficients of the canonical $f$ polynomials are positive. We also use the deformation-invariance of $f$ to prove that the polynomial $p$ is congruent modulo 2 to a power of the sum of its variables.

preprint2020arXiv

Germ order for one-dimensional packings

Every set of natural numbers determines a generating function convergent for $q \in (-1,1)$ whose behavior as $q \rightarrow 1^-$ determines a germ. These germs admit a natural partial ordering that can be used to compare sets of natural numbers in a manner that generalizes both cardinality of finite sets and density of infinite sets. For any finite set $D$ of positive integers, call a set $S$ " $D$ -avoiding" if no two elements of $S$ differ by an element of $D$ . We study the problem of determining, for fixed $D$ , all $D$ -avoiding sets that are maximal in the germ order. In many cases, we can show that there is exactly one such set. We apply this to the study of one-dimensional packing problems.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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