User steve flammia - MathOverflow

Distribution of 1-norm for Gaussian Unitary Ensemble

2009-10-26T18:33:18Z

Suppose I uniformly sample matrices X from the Gaussian Unitary Ensemble (GUE) with variance \sigma^2. Consider the Ky-Fan d norm, i.e. the sum of the singular values, of X. Let's call this Z=||X||_1. What is the distribution of Z as a function of the dimension d and the variance \sigma^2? Really, all I want are estimates of the mean and a good tail bound, so maybe also the second moment.

Field extension containing the eigenvectors of a Hermitian matrix

2009-12-18T16:38:10Z

Let H be a (finite-dimensional) Hermitian matrix with algebraic numbers for its entries, all of which lie in some minimal field extension of the rational numbers; call this field ℚ(H) for short. Let's assume that the eigenvalues of H are distinct, and let D be the diagonal matrix of eigenvalues of H in non-increasing order, say. Since H is Hermitian with a non-degenerate spectrum, there is a unique unitary matrix U that diagonalizes H. The normalized eigenvectors of H comprise the columns of U. Finally, let ℚ(U,D) be the field extension of the rationals containing the matrix elements of U and D.

Is there any relationship between ℚ(H) and ℚ(U,D)? In particular, I would like to know a bound on the degree of ℚ(U,D)/ℚ(H). Also if possible, is there a way to take H (without diagonalizing it!) and calculate ℚ(U,D)? I'd also be happy with something that contains ℚ(U,D) and isn't that much bigger. (I mean, its only bigger by a factor that is constant or depends on the dimension, not on the particular H.)

Are two probability distributions uniquely constrained by the sum of their p-norms?

2009-12-09T19:49:41Z

Let A, B and C be finitely supported probability distributions with at most d nonzero probabilities each. Now consider the following simultaneous equations using p-norms, for each value of p≥1, given by

||A||_p + ||B||_p = ||C||_p

where A, B and C are still non-negative, but we relax normalization on A and B. Imagine that C is fixed and, without loss of generality, normalized. We want to solve for A and B.

First, note that one obvious family of solutions is

A = (1-x) C , B = x C , 0≤x≤1 .

Question: Ignoring the obvious permutation symmetries, are these the only solutions?

Edit: By p-norm, I mean the vector p-norm: ||A||_p = (∑_j |a_j|^p )^1/p. Although we don't really need the absolute values, since the a_j are all non-negative.

Answer by Steve Flammia for Eigenvalues of a sum of Hermitian positive definite circulant matrix and a positive diagonal matrix

2012-06-06T00:28:43Z

This was too long to fit as a comment. I have no idea if this helps, but here's an observation.

Let $X$ denote the matrix which cyclicly permutes the columns in the standard basis by one unit, and $Z = FXF^*$ be it's Fourier transform (using a unitary normalization). Then $X$ and $Z$ form a representation of the Heisenberg group over the ring $\mathbb{Z}/n$. We have $X^n = Z^n = \omega^n = 1$, where $\omega = e^{2\pi i/n}$, and $XZ=\omega ZX$. The elements of the form $X^iZ^j$ form a basis for $n\times n$ matrices which is orthogonal in the trace inner product and is unitary. Your matrices $C$ and $D$ can be expanded as $C = \sum_{j\in\mathbb{Z}/n} \lambda_j X^j$ and $D = \sum_{k\in\mathbb{Z}/n} d_k Z^k = \sum_{k\in\mathbb{Z}/n} d_k F X^k F^*$. Perhaps there is some way to leverage this observation to generate constraints, maybe by estimating powers of $C+D$?

Generating a group by randomly sampling generators

2012-05-23T19:51:15Z

Let $G$ be a finite abelian group, $n$ a positive integer and let $G^n$ denote the direct product of $n$ copies of $G$. We say an element of $G^n$ is full if it acts as a nonidentity element of $G$ in each of the factors of $G^n$.

Now consider the following random process. Sample a full group element $(g_1,g_2,\ldots,g_n)$ uniformly at random from $G^n$. Now generate a subgroup $H$ of $G^n$ consisting of all elements of the form $\bigl(g_1^{a_1},\ldots,g_n^{a_n}\bigr)$ for integers $a_i$. If we do this $k$ times (sampling with or without replacement, more on this below), then we can let $H_j$ denote the subgroup generated on the $j$th iteration. Now we take the union of these subgroups and define $$ N_k = \left| \bigcup_{j=1}^k H_j \right| \ ,$$ where $|\cdot|$ denotes the cardinality of the set. Finally, let $\mu_k = \mathbb{E}(N_k)$.

When $G$ is also a simple group, this is easy to calculate. So let's specialize to the simplest nontrivial case, $G = \mathbb{Z}/2 \times \mathbb{Z}/2$. (The other simplest case is $\mathbb{Z}/4$, but I'm not as interested in that one.) Then my question is,

How does $\mu_k$ grow as a function of $k$?

I am principally interested in lower bounds on $\mu_k$ in the case where the sampling is done uniformly without replacement on the set of full elements of $G^n$. Clearly sampling with replacement gives a lower bound, and it's much easier to work with. If you can say something about the variance of $N_k$ too, that would be outstanding.

Answer by Steve Flammia for Generating a group by randomly sampling generators

2012-05-26T05:57:07Z

Let's get a lower bound by considering sampling with replacement, for which we can even get the exact answer. If we sample $k$ full elements, what is the probability that they agree at exactly $l$ locations? For $G = \mathbb{Z}/2 \times \mathbb{Z}/2$, the answer is $$ p(k,l) = {n \choose l} \left(\left(\frac{1}{3}\right)^{k-1}\right)^l \left(1-\left(\frac{1}{3}\right)^{k-1}\right)^{n-l}. $$ When two full elements agree in exactly $l$ places, they jointly generate $2\times2^n - 2^l$ elements of $G^n$. Continuing this logic, an inclusion-exclusion principle lets us count the expected number of elements after $k$ steps, namely, $$ \mu_k = \sum_{j=1}^k {n \choose j} (-1)^{j-1} \sum_{l=0}^n p(j,l) 2^l . $$ This formula isn't very nice because when $k$ is large we have to sum over as many as $3^n$ terms. Fortunately, we can use the binomial theorem twice to get rid of the sum on $j$. We first expand the binomial term in $p(j,l)$, then collapse the sum on $j$. The result is $$ \mu_k = 4^n - \sum_{l=0}^n \sum_{m=0}^{n-l} {n \choose l} {n-l \choose m} (-3)^m 6^l \bigl(1-3^{-(l+m)}\bigr)^k . $$ This is much easier to evaluate than the previous formula.

While this bound is really good for small $k$, it is not good for very large $k$. Since $\mu_k$ is concave in $k$ (see the comments in Will Sawin's answer), the convex hull of two lower bounds is again a lower bound. So we can add in the fact that the point $(3^n,4^n)$ is the answer for sampling without replacement and find the line which connects this point back to the previous bound in an optimal way. This is hard to do analytically, but can be done for specific values of $n$. This gives a very good lower bound.

Bounding a spectral gap: what proof techniques exist?

2010-04-08T13:51:13Z

The following situation is ubiquitous in mathematical physics. Let $\Lambda_N$ be a finite-size lattice with linear size $N$. An typical example would be the subset of $\mathbb{Z}\times\mathbb{Z}$ given by those pairs of integers $(j,k)$ such that $j,k \in$ { $0,\ldots,N-1$}. On each vertex $j$ of the lattice place a copy of the vector space $\mathbb{C}^d$. The total space will be the tensor product of all of these spaces. Then define a Hamiltonian acting on this total space as follows: $$ H = \sum_{k \in \Lambda_N} h_k$$ for some Hermitian matrices $h_k$ which act like the identity everywhere except on the vector spaces located on site $k$ and in the neighborhood surrounding $k$. Typically, one is interested in the case where there is a translational symmetry (except at the boundary) in the definition of the $h_k$. Denote the eigenvalues of $H$ in increasing order by $\lambda_1 \le \lambda_2 \le \ldots \le \lambda_M$.

For an arbitrary fixed family of Hamiltonians $H$, what proof techniques exist for computing an upper and a lower bound on $\Delta = \lambda_2 - \lambda_1$ as a function of $N$? In particular, we want to know if $\Delta$ decays to zero as a function of $N$, or if it is lower-bounded by some constant independent of $N$.

The gap $\Delta$ is the energy gap between the ground state and the first excited state of an interacting quantum system. Understanding this quantity tremendously impacts our understanding of the different phases of matter, but it is extremely difficult to compute or even bound for all but the simplest cases (like when all the $h_k$ commute). This difficulty persists even when there is significant additional (physically motivated) structure in the problem, such as considering only $h_k$ which are projectors, and where there is a unique zero-energy eigenstate (all others having positive energy for any finite $N$).

More general formulations of this question also have applications to expansion properties of graphs, mixing times of Markov chains, and many other things. I’m happy to hear answers related to these as well, but I’m hoping to find answers that are useful for the structure of local Hamiltonians, as defined above.

Answer by Steve Flammia for Proofs without words

2009-12-14T15:35:33Z

Wikipedia has a few nice proofs of the pythagorean theorem. Elementary, but elegant.

Answer by Steve Flammia for Generalization of scalar product to k-dimensional subspaces (as opposed to 1-dimensional subspaces, i.e. vectors)

2011-05-30T13:55:28Z

There is a very simple way to do this which is to consider the projector onto each subspace, $\Pi_A$ and $\Pi_B$, where we have $$\Pi_A = \sum_j a_j a_j^T$$ and similarly for $\Pi_B$. Since all of your vectors spanning your subspace are orthogonal and normalized, this is indeed a rank-$k$ projector. Then you can just consider the Hilbert-Schmidt inner product, $$\langle A , B \rangle = \mathrm{Tr}(A^T B)$$ and this will give you a measure of how similar the two spaces are. If you first divide each projector by the square root of it's rank, then this quantity is normalized so that it is 1 if and only if the two subspaces are equal.

Answer by Steve Flammia for Toy Models of Quantum Mechanics

2011-03-20T16:34:45Z

Regarding finite field versions of quantum mechanics, the following paper is a good place to start:

"Modal quantum theory", by Schumacher & Westmoreland, arXiv:1010.2929

In this paper, the authors present a discrete model of quantum theory that is similar to standard quantum mechanics, but it is based on finite field-valued amplitudes instead of complex amplitudes. The theory is surprisingly rich: it allows for entangled states and contains versions of the no-cloning theorem and Bell's theorem. It also has a distinctly different flavor when it comes to probabilities, namely (as the title suggets) it deals only with modality, the possibility or necessity of an outcome, rather than probability measures.

There is at least one other program for studying toy theories which comes to mind. These go by the name of "general probabilistic theories" or "convex operational theories". Here the idea is to replace quantum mechanics with a general convex space which becomes the space of quantum states. Then you decorate this space with things like tensor products to define composite systems and so on. It lets you ask questions about why quantum mechanics is special, since only some of the things we think of as being quintessentially "quantum" can be done in these other theories. In this regard, they do indeed shed important light on the nature of quantum mechanics.

The names I most associate to this approach are Barnum, Barrett, Leifer and Wilce, though I may have forgotten some others. Searching the quant-ph arxiv will turn up some papers for you. One which I've read personally, and it should get you started, is

"Information processing in convex operational theories", Barnum & Wilce, arXiv:0908.2352

Extremal Obstructions to Gowers Uniformity

2011-01-25T21:15:27Z

Recall the definition of the Gowers uniformity norm $\|f\|_{U^{k}(G)}$ , \begin{align} \|f\|_{U^{k}(G)} := \left( \mathbb{E}_{x,h_1,\ldots,h_k \in G} \Delta_{h_1} \ldots \Delta_{h_{k}} f(x) \right)^{2^{-k}} \, \end{align} where the operator $\Delta_h$ is a multiplicative analog of a derivative given by \begin{align} \Delta_h f(x) := f(x+h) \overline{f(x)} \,, \end{align} and $G$ is a finite abelian group. I'm specifically interested in the case $G=\mathbb{Z}_d$ of integers modulo $d$, and $k=3$. Therefore, I'll just use the shorthand notation $\|f\|_{U^{k}(\mathbb{Z}_d)} = \|f\|_{U^{k}}$ .

I'm interested in functions $f:\mathbb{Z}_d \to \mathbb{C}$ which have some fixed value of $\|f\|_2$, say 1, meaning that \begin{align} \|f\|_2^2 = \sum_{h \in \mathbb{Z}_d} f(h) \overline{f(h)} = 1\,. \end{align}

Then my question is,

What are the functions having unit 2-norm which minimize $\|f\|_{U^3}$?

I can prove a lower bound of $\|f\|^8_{U^3} \ge \frac{2}{d^{4} (d+1)}$ , so such functions cannot have arbitrarily small Gowers norm. This bound seems to be tight for all values of $d$ (via numerics) but there is no obvious function which provably saturates the bound for all $d$.

From what I can tell, it appears that such obstructions to Gowers uniformity, like the 2-norm constraint above, have been studied before. But I cannot tell if such extremal problems have been studied, or even if they are thought to be tractable.

How many simply connected subsets of an n-by-m grid?

2010-10-29T17:59:50Z

Given an n-by-m square grid graph, how many ways are there to choose a subset of the vertices which is simply connected? Here, a subset of vertices is simply connected if the vertices, together with any edges or interior faces connecting them amongst themselves, form a contractible subregion of the grid. More formally, we can naturally embed the grid graph into the plane. Then I want to count subsets of vertices such that the union of the dual 2-cells forms a simply connected region in the plane.

Let me try to be a little bit clearer this time. Let's work directly with the dual, since that is easier to visualize. Hence, my question is:

Consider a grid of square tiles of dimensions n-by-m, with each of the nm tiles distinctly labeled. How many distinct (labeled) simply connected subsets of tiles are there as a function of n and m?

Because the tiles are labeled, rotation or translation to get the same polyomino isn't allowed. I'm trying to count all subsets. Commenter JBL points out the sequence for m=n at Sloane's, which also links to a lot of work by Artem M. Karavaev on this problem.

Answer by Steve Flammia for Bounding a spectral gap: what proof techniques exist?

2010-04-08T13:56:33Z

Bounding angles in projector-valued Hamiltonians

Suppose that each of the $h_k$ are projectors, and suppose that we shift the total energy so that $\lambda_1 = 0$. Further suppose that this eigenspace is known to be non-degenerate for every finite $N$. Then one proof technique that sometimes works (at least in one dimension, but it can be generalized) to prove an $N$-independent lower bound is the following, which to the best of my knowledge was first discussed in

M. Fannes, B. Nachtergaele, R. F. Werner, Finitely correlated states on quantum spin chains, Comm. Math. Phys. Vol. 144, Num. 3 (1992), 443-490. MathSciNet:MR1158756

The bound is as follows. Let $\theta_{j,k}$ be the smallest non-zero angle between the pair of projectors $h_j$ and $h_k$. That is, $\cos^2(\theta_{j,k})$ is the largest eigenvalue not equal to one of $h_j h_k h_j$. Define $\theta = \min_{j,k} \theta_{j,k}$. Then FNW show that $$ \Delta \ge 1-2 \cos(\theta) .$$ As long as $\cos(\theta)$ is less than 1/2, there is an $N$-independent lower bound on $\Delta$, since this involves only local information. The proof proceeds by squaring $H$ and then bounding how negative the anti-commutators can be by using this angle $\theta$.

Answer by Steve Flammia for What's your favorite equation, formula, identity or inequality?

2010-07-15T15:27:43Z

The Euler-Lagrange equations, $$\frac{\partial L}{\partial q_j} = \frac{d}{dt}\frac{\partial L}{\partial \dot{q}_j}$$

Answer by Steve Flammia for What is the entropy of a density matrix which is the sum of two unitarily equivalent projectors?

2010-06-17T17:13:46Z

First observation, you can unitarily rotate the first term without changing the spectrum so you can just consider a single unitary with out loss of generality. Call the rotated term $Q$.

Next, it helps to know about the canonical form for two projectors. Given two projectors P and Q in general position, you can always compute the eigenvalues of P+Q as follows. They are simply $1 \pm x_j$ where the $x_j$ are the positive square roots of the eigenvalues of the operator $PQP$ (or $QPQ$... it doesn't matter).

For your problem, because of the tensor product structure, this is actually quite easy to do. The eigenvalues $x_j$ will be all possible products of the local eigenvalues for $P^{(i)} Q^{(i)} P^{(i)}$, with a square root. The entropy is then a sum over these configurations, suitably normalized.

Simultaneous time-frequency concentration of orthonormal sequences?

2010-03-12T03:31:13Z

Does there exist an orthonormal basis of square-integrable functions (either $L^2(\mathbb{R})$ or $L^2(\mathbb{C})$) such that the sequence of functions has bounded variance, and also the sequence consisting of the Fourier transform of each function also has bounded variance?

Some background:

This question came up in a comment on SciRate regarding a recently translated paper by von Neumann. There the commenter, Matt Hastings, points out some related results.

In particular, the Balian-Low theorem states that this can't exist for any Gabor basis, i.e. one which is composed of time and frequency translates of a given fiducial $L^2$ function. If there were a generalization of this theorem to arbitrary bases, it would prove that such a sequence can't exist.

Answer by Steve Flammia for How hard is it to compute the number of prime factors of a given integer?

2009-12-29T15:15:11Z

Just a few simple observations which haven't been pointed out yet. First, you can phrase the question as a decision problem: Does the integer N have greater than k prime factors (distinct or otherwise)? Then you can use binary search to efficiently find the exact number of prime factors by asking repeated questions. As you point out, this is easier than factoring. Regarding particular complexity classes, this problem is in BQP (bounded-error quantum polynomial time) since we can just use Shor's algorithm to efficiently factor the number first. It's also in the intersection of co-NP and NP, since whichever answer we get (whether it has at least k prime factors, or less than k) can be verified efficiently on a classical computer. There might be more specialized complexity classes where one could try to fit this problem... the first place to look is the Complexity Zoo.

Answer by Steve Flammia for Range of binomial probability, given a certain number of observations?

2009-12-23T04:32:55Z

Some very sharp bounds for questions like these are provided by something called a Chernoff bound. The example in the wikipedia article will give you what you need.

Edit: Oh, I forgot to say that you need an estimator for the "true" probability, but I guess that the one you are using is just the average over the samples.

Answer by Steve Flammia for How to construct matrices with periodicity

2009-12-22T17:26:01Z

I'm guessing you didn't mean for the size of the matrix and the period to be equal, so let's assume that the matrix is k-by-k. For any such matrix, the eigenvalues must be nth roots of unity. Then you can construct families of such matrices by picking k different nth roots of unity, and then conjugating this by any invertible matrix. To be more explicit, pick k different numbers of the form $\omega_j = \exp(2 \pi i a_j/n)$ where each a_j is an integer between 0 and n-1 of your choice, for j=1,...,k. Then form the matrix $\Lambda$ whose diagonal elements are $\Lambda_{jj} = \omega_j$, and pick an arbitrary invertible matrix $S$ and form $S \Lambda S^{-1}$.

Answer by Steve Flammia for How is it that you can guess if one of a pair of random numbers is larger with probability > 1/2?

2009-12-15T22:04:43Z

There is a related "paradox" known as the two envelopes problem which has a nice article on wikipedia.

A group action of the Heisenberg group with special symmetries

2009-10-27T21:26:49Z

Suppose we look at the Heisenberg group H_d as a matrix group of upper triangular matrices over the ring ℤ/dℤ. You can even choose d to be prime if you want. A natural irrep of H_d acting on ℂ^d maps the group elements into the "shift" and "phase" operators, plus roots of unity. More specifically, the two natural generators map the orthonormal basis vectors from j \to j+1 mod d, and the Fourier transform of that operation, plus overall phases by roots of unity. The question is this:

Can you find a unit vector v such that |(v,U_g v)| = c for all g not in the center of H_d? One can solve for the constant: c=1/sqrt(d+1).

Numerics suggests that these vectors exist in all the dimensions < 67, hence they may exist in every dimension, but the form of the vectors contains no (obvious) hint as to how to prove this.

This problem seems extremely truculent and any help is greatly appreciated!

How much faith should I put in numerics?

2009-11-29T23:48:56Z

Edit: Let me summarize what this question was meant to ask. Is there a quantitative theory of "approximate" soundness? Arguments are usually either sound or unsound. This is binary. If we don't have access to a complete argument, or are unsure whether to trust parts of an argument, can we come up with a number between 0 and 1 that quantifies how sound the incomplete or untrusted argument is?

Original rambling question below:

Before getting to the question, let me first try to make a rough distinction in what I mean by numerics. There are several types, and I'll begin with what I don't mean by numerics: something like numerical integration, or numerical root finding. I consider this zeroth case uninteresting. Problems like these are completely understood. We are just using computers to do our tedious calculations for us, and I see no reason not to trust the result.

For the first type, I'm thinking of large complex calculations such as those used in the four color theorem, or the recent proof that checkers is a draw, or maybe the recent work on the character table for split E₈. Here there are just a finite number of cases to be checked, but the computation itself is extremely elaborate just to compute about one bit of information (in the first two cases). For these types of problems, I'm imagining that there is no known way to generate a certificate that would reduce checking the validity of the calculation to an instance of case 0 numerics.

For the second type, consider numerics of the following flavor. In this scenario, my friend Bernhard has a conjecture that all of the infinitely many non-trivial zeros of a certain function lie on a certain line in the complex plane. Unfortunately, I'm not as good as Bernhard, and I don't understand his insight in proposing the conjecture. Lacking his intuition, and in lieu of a proof, I decide to numerically test the conjecture. I find that the first 10¹⁰ zeros (say) all line on the correct line.

Now I can start to get to the question. First of all, there is a fuzzy line between case 0 and case 1. Is there a way to make this line more precise?

Next, can we make precise the notion of "trusting" large calculations of the type 1 variety? How much should we trust them? Also, these types of calculations can be very unsatisfying if they don't lead you to a principle which explains why the answer is what it is. Is there a way to make this notion precise as well? Suppose that the proof of the four color theorem could be reduced to checking only 31 cases, instead of several hundred, but a computer was still necessary. Would we consider this a "good" proof? I would like to try to quantify this.

Finally, consider case 2. Have we really given any support at all to the conjecture if we've left an infinite number of cases unchecked? I'm tempted to answer a knee-jerk "No!" to this, especially in light of things like the disproof of the Mertens conjecture or Skewes' number. But it certainly feels like we've made it more plausible than if we hadn't checked those cases. I'm afraid we might have to resort to Bayesian degrees of belief here, but is there another answer?

Answer by Steve Flammia for How much faith should I put in numerics?

2009-11-30T02:45:34Z

It's pretty clear that I didn't do a good job asking this question, because it seems I'm confusing people. Let me offer a more detailed example which tries to constructively answer this question.

Consider the notion of a probabilistically checkable proof (PCP). In this setting, we can take a formalized argument and process it into a new argument whereby we only need to check a few bits of the proof to be sure with high probability that the argument is correct. One answer that I would find very satisfying, would be if there were some way we could make this construction completely canonical, so that there would be a clear notion of "how much" you need to process an argument before you accept it's claim with probability 1-ε. Then, I'm imagining that we could compare two different proofs of the same theorem by asking how much do we have to process them to get the same confidence 1-ε. Presumably this amount of processing would make some proofs more "believable" than others with the same resources.

I hope this starts to get to the heart of what I was trying to ask.

Answer by Steve Flammia for Famous mathematical quotes

2009-11-29T20:38:35Z

A mathematician is a device for turning coffee into theorems. —Alfréd Rényi, but often attributed also to Paul Erdős

Finding the new zeros of a "perturbed" polynomial

2009-11-23T15:42:46Z

Given a univariate polynomial with real coefficients, p(x), with degree n, suppose we know all the zeros x_j, and they are all real. Now suppose I perturb each of the coefficients p_j (for j ≤ n) by a small real perturbation ε_j. What are the conditions on the perturbations (edit: for example, how large can they be, by some measure) so that the solutions remain real?

Some thoughts: surely people have thought of this problem in terms of a differential equation valid for small ε that lets you take the known solutions to the new solutions. Before I try to rederive that, does it have a name? This seems like a pretty general solution technique, but perhaps it is so general as to be intractable practically, which might explain why I don't know about it.

If you ignore the smallness of the perturbation, then there is a general question here which seems like it might be related to Horn's problem: given two real polynomials p(x) and q(x) of degree n and their strictly real roots, what can you infer about the roots of p(x)+q(x)? This question is very interesting and I would love to hear what people know about it. But I'm also happy with the perturbed subproblem above, assuming it is indeed simpler.

Answer by Steve Flammia for Online Graphing Sites

2009-11-23T15:46:37Z

Wolframalpha.com is quite useful in this regard.

Answer by Steve Flammia for How Does Random Noise Typically Look?

2009-11-15T13:17:00Z

I think that there is a point of possible confusion with what it means to say there is an error. When I think about a noise process on a quantum system, I think of the following. Given an initial state $\rho$ of the system, the noise process is a completely positive map $\mathcal{E}$ that produces the output state $\sigma = \mathcal{E}(\rho)$. So, unless the channel is the identity channel, then there is always something nontrivial happening (for at least some choice of initial state $\rho$). So has an error occurred? In some sense, yes. Even if the channel has an operator decomposition where a large fraction of the support of the channel is on the identity channel, then there is in general always an error. I think the point of confusion is that for these types of channels, when you measure the state it will collapse into either a state with no error, or a state with (potentially) lots of errors. So, yes, the errors are highly correlated. But the channel is trying to model some kind of conditional independence. Upon measurement, you think of the channel as either having acted trivially, or having done something bad, like apply a randomly sampled Pauli error. Conditioned on something bad happening, then you have independence.

(For anyone unfamiliar with quantum channels, a classical model showing this kind of behavior would be a kind of "catastrophic loss" channel, where you put all $n$ bits into the channel, and with probability $1-\epsilon$ they are faithfully transmitted, and with probability $\epsilon$ you throw away the bit string and replace it with noise, c.f. something sampled uniformly from the hypercube.)

Also, following up on Gil's comment in Greg's answer, one obvious way to define a random stochastic map would be to just pick random probability distributions and make them the rows of a stochastic matrix. Picking a random distribution could be done by choosing your favorite measure on the simplex whose points are labeled by bit strings. You'd still have to decide how to choose the dependencies between rows. Even under the simple and natural case of uniform measure and independently chosen rows, it is not clear to me how this looks.

When to pick a basis?

2009-11-08T16:48:59Z

Picking a specific basis is often looked upon with disdain when making statements that are about basis independent quantities. For example, one might define the trace of a matrix to be the sum of the diagonal elements, but many mathematicians would never consider such a definition since it presupposes a choice of basis. For someone working on algorithms, however, this might be a very natural perspective.

What are the advantages and disadvantages to choosing a specific basis? Are there any situations where the "right" proof requires choosing a basis? (I mean a proof with the most clarity and insight -- this is subjective, of course.) What about the opposite situation, where the right proof never picks a basis? Or is it the case that one can very generally argue that any proof done in one manner can be easily translated to the other setting? Are there examples of proofs where the only known proof relies on choosing a basis?

Answer by Steve Flammia for probabilistic knot theory

2009-10-30T18:52:20Z

One possible route to a model of random knots would be through the braid group. Every knot can be expressed (non-uniquely) as the closure of a braid. So, for example, you could apply the braid generators uniformly $n$ times across $k$ strands, close the braid using your favorite closure, and then ask this question sensibly. I don't think you can directly ask about the $n \to \infty$ limit for the braid group, though, because I don't think there is a notion of uniform measure for that group. Actually, perhaps I will post this as a separate question, but is the braid group amenable? I would wager that in this model, the probability of having the unknot decreases very quickly with $n$ and $k$.

To test if you have the unknot, it is conjectured that you just have to check the Jones polynomial. But even this is still hard in general, ~~unless~~ even if you happen to have a quantum computer. :)

(Edit: Thanks Greg Kuperberg, below, for the correction.)

When are probability distributions completely determined by their moments?

2009-10-31T09:57:27Z

If two different probability distributions have identical moments, are they equal? I suspect not, but I would guess they are "mostly" equal, for example, on everything but a set of measure zero. Does anyone know an example of two different probability distributions with identical moments? The less pathological the better. Edit: Is it unconditionally true if I specialize to discrete distributions?

And a related question: Suppose I ask the same question about Renyi entropies. Recall that the Renyi entropy is defined for all a ≥ 0 by

H_a(p) = log(∑_j p_j^a)/(1-a)

You can define a=0,1,∞ by taking suitable limits of this formula. Are two distributions with identical Renyi entropies (for all values of the parameter a) actually equal? How "rigid" is this result? If I allow two Renyi entropies of distributions p and q to differ by at most some small ε independent of a, then can I put an upper bound on, say, || p - q ||₁ in terms of ε? What can be said in the case of discrete distributions?

Comment by Steve Flammia

2012-05-24T18:58:38Z

A similar linear upper bound is $2^n k$, which is tighter for small $k$. These are all fantastic, but do you think it might be possible to get a strictly concave lower bound? The linear ones are not quite strong enough for my purposes, unfortunately.

Comment by Steve Flammia

2012-05-24T03:50:23Z

Yes, of course. (I read "with" instead of "without".) In fact, $k \le 3^n$, the number of full elements in $G^n$. Then $N_{3^n} = 4^n \gg 3^n$. In that case, it seems the bound is rather loose, no? Plus one regardless!

Comment by Steve Flammia

2012-05-24T00:51:44Z

I lost you after the first line... $N_k \le |G|^n = 4^n$ for all k, so the bound your wrote can't always hold.

Comment by Steve Flammia

2012-05-23T21:44:55Z

@Gerhard, yes, you're right. I meant simple, sorry. Fixed.

Comment by Steve Flammia

2011-05-30T13:58:54Z

Actually, this reduces to the squared inner product when $k=1$. So perhaps this isn't what you want.

Comment by Steve Flammia

2011-03-20T20:12:58Z

@Daniel, thanks! Hopefully our comments will spur PEV into clarifying his/her question.

Comment by Steve Flammia

2011-03-20T19:51:26Z

(cont.) A toy theory is then a mathematical framework distinct from QM but which captures some essential features of QM regardless. From the example in the question about finite fields, I gather this is the intent of the question: to find theories which are distinct from standard QM that nonetheless illuminate the standard theory. By contrast, your answer provides "only" an example from standard QM (albeit a very nice one). Admittedly, though, I think our disagreement comes only from the vagueness of the question.

Comment by Steve Flammia

2011-03-20T19:46:26Z

@Daniel, I agree that finite dimensional Hilbert spaces simplify the theory. Qiaochu's post and your answer are great in that they provide basic examples of quantum mechanics. If this is what PEV is asking, then I also offer systems like the harmonic oscillator, a free particle in 1d, and even two spin-1/2 particles as other "toy models". All of these fit squarely within standard QM theory, and anyone interested in learning standard QM should study them. However, I interpret the question as asking for models that are distinct from standard QM. Let's call these toy theories... (cont.)

Comment by Steve Flammia

2011-03-20T17:27:35Z

@Qiaochu, yes you're right; I read the question too hastily. Please see my comment at the top, though. Your blog post is a great example of regular quantum mechanics, which I think isn't the spirit of the question.

Comment by Steve Flammia

2011-03-20T17:06:33Z

I think what you are after is better called a toy theory, i.e. a theory which is distinct from regular quantum mechanics, but still exhibits structural similarities that helps us gain insight into the standard theory. This would preclude other examples (harmonic oscillator, transverse field Ising model, quantum walks on graphs etc.) which would qualify as "toys" in the sense that they are simple to analyze models of regular quantum mechanics.

Comment by Steve Flammia

2011-03-20T16:26:13Z

I don't see how this is relevant. The linked blog post still has wavefunctions defined over the complex numbers. It seems that PEV is asking about wavefunctions taking values over finite fields.

Comment by Steve Flammia

2011-03-02T00:44:04Z

You need to specify how you are choosing your random graph, otherwise this isn't a well-posed question. Do you mean over the uniform distribution over all graphs with n vertices and k edges?

Comment by Steve Flammia

2011-01-31T23:34:28Z

Since the solutions are numerical, they don't really have a useful form. An analytic solution for d=2 is: $f(0)=\sqrt{3+\sqrt{3}}$ , and $f(1) = \sqrt{3-\sqrt{3}} e(1/8)$. I can email you a few other examples for larger d if you want. I haven't checked if they can be formed from sums over polynomial phase functions, because I don't know how to check this when the phase functions are nonlinear. Is there a way to get a "nonlinear Fourier decomposition" of a function?

Comment by Steve Flammia

2011-01-31T02:54:14Z

Thanks Thomas! I guess this upper bound only works in prime dimensions, though, right? Unfortunately, these functions don't look anything like the ones which are actual extreme points, so I don't see how to get there from here. The ones which minimize don't ever seem to have a constant absolute value like the phase function you've proposed. It's maddeningly close to the lower bound, though.

Comment by Steve Flammia

2010-11-02T18:49:08Z

I revamped the question a bit... hopefully this is clearer now.