Different permutations are almost orthogonal

Add to your list(s) Download to your calendar using vCal

• Aram Harrow (University of Washington)
• Friday 13 July 2012, 12:00-13:00
• MR14, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Richard Jozsa.

Consider the n! different unitaries that permute n d-dimensional quantum systems. If d>=n, then these are linearly independent. In this talk, I’ll explain a sense in which they are approximately orthogonal if d >> n^2. This simple fact turns out to make life much easier when working with multipartite quantum states that are invariant under collective unitary rotation. After describing the basic idea, I’ll discuss some subset of the following five applications:

1. There is no efficient product test (in the sense of my previous work with Ashley Montanaro) that uses only LOCC measurements between the different copies of the state to be tested.

2. Random maximally entangled states have similar moments to fully random states.

3. Random quantum circuits on n qubits with poly(n) gates are approximate poly(n)-designs. (Joint work with Fernando Brandao and Michal Horodecki).

4. An alternate proof of the Hastings result that random unitaries give quantum expanders.

5. The N-party data-hiding scheme of Eggeling and Werner can be achieved with only poly(N) local dimension.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR14, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.