Black Holes and Complexity Classes

Beni Yoshida Feb 13 2018 19:53 UTCAbhinav Deshpande Feb 10 2018 15:42 UTC

...(continued)I see. Yes, the epsilon ball issue seems to be a thorny one in the prevalent definition, since the gate complexity to reach a target state from any of a fixed set of initial states depends on epsilon, and not in a very nice way (I imagine that it's all riddled with discontinuities). It would be inte

Elizabeth Crosson Feb 10 2018 05:49 UTC

...(continued)Thanks for the correction Abhinav, indeed I meant that the complexity of |psi(t)> grows linearly with t.

Producing an arbitrary state |phi> exactly is also too demanding for the circuit model, by the well-known argument that given any finite set of gates, the set of states that can be reached i

Abhinav Deshpande Feb 09 2018 20:21 UTC

...(continued)Elizabeth, interesting comment! Did you mean to say that the complexity of $U(t)$ increases linearly with $t$ as opposed to exponentially?

Also, I'm confused about your definition. First, let us assume that the initial state is well defined and is $|\psi(0)\rangle $.

If you define the complexit

Elizabeth Crosson Feb 08 2018 04:27 UTC

...(continued)The complexity of a state depends on the dynamics that one is allowed to use to generate the state. If we restrict the dynamics to be "evolving according a specific Hamiltonian H" then we immediately have that the complexity of U(t) = exp(i H t) grows exponentially with t, up until recurrences that

Danial Dervovic Feb 05 2018 15:03 UTC

...(continued)Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

Michael A. Sherbon Feb 02 2018 15:56 UTC

...(continued)Good general review on the Golden Ratio and Fibonacci ... in physics, more examples are provided in the paper “Fine-Structure Constant from Golden Ratio Geometry,” Specifically,

$$\alpha^{-1}\simeq\frac{360}{\phi^{2}}-\frac{2}{\phi^{3}}+\frac{\mathit{A^{2}}}{K\phi^{4}}-\frac{\mathit{A^{\math

Māris Ozols Feb 01 2018 17:53 UTC

...(continued)This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

Johnnie Gray Feb 01 2018 12:59 UTC

Thought I'd just comment here that we've rather significantly updated this paper.

wenling yang Jan 30 2018 19:08 UTC

off-loading is an interesting topic. Investigating the off-loading computation under the context of deep neural networks is a novel insight.

Luhao Wang Jan 30 2018 00:28 UTC

well written paper! State-of-art works that are good to publish to some decent conferences/journals

mahdi aliakbari Jan 29 2018 20:49 UTC

Very well written paper with formal problem formulation and extensive results on multiple benchmarks

aaditya prakash Jan 29 2018 19:58 UTC

Code is available here: https://github.com/iamaaditya/pixel-deflection

Faraz Rabbani Jan 29 2018 07:53 UTC

Interesting case study for computation offloading

Marco Piani Jan 28 2018 11:21 UTC

...(continued)Hi Mizanur,

thanks to you for taking into account my comment. I am not sure of the jargon and nomenclature in mathematics; are/were the maps that are completely positive and also completely co-positive known as PPT maps? What I was pointing out is that in the quantum information community the nam

Mizanur Rahaman Jan 27 2018 19:06 UTC

...(continued)Hi Marco, thanks for pointing out the possible confusion. I will make it clear in the revised version. I think in this context what I should clearly state is that I am considering linear maps

which are completely positive and co-completely positive, that is, the map \Phi and \Phi\circleT

are compl

Marco Piani Jan 24 2018 03:34 UTC

...(continued)Great work! One thing that might potentially confuse readers is the use of "PPT channel" to indicate that the partial action of the channel produces a PPT state. There might be some ambiguity in literature, but many call "PPT channels" those channels that act jointly on two parties, and that preserv

Mizanur Rahaman Jan 23 2018 23:20 UTC

Thanks for the comment. I was not aware of the "entanglement breaking index" paper.

I will include it in a revised version. I will make a remark about the other deduction as well.

Thanks.

Ludovico Lami Jan 19 2018 00:08 UTC

...(continued)Very nice work, congratulations! I just want to point out that the "index of separability" had already been defined in arXiv:1411.2517, where it was called "entanglement-breaking index" and studied in some detail. The channels that have a finite index of separability had been dubbed "entanglement-sa

Blake Stacey Jan 17 2018 20:06 UTC

...(continued)Eq. (14) defines the sum negativity as $\sum_u |W_u| - 1$, but there should be an overall factor of $1/2$ (see arXiv:1307.7171, definition 10). For both the Strange states and the Norrell states, the sum negativity should be $1/3$: The Strange states (a.

Steve Flammia Dec 18 2017 20:59 UTC

It splits into even and odd cases, actually. I was originally sloppy about the distinction between integer and polynomial division, but it's fixed now. There is a little room left in the case $d=3$ now though, but it's still proven in every other dimension.

Aram Harrow Dec 18 2017 19:30 UTC

whoa, awesome! But why do you get that $d^3-d$ must be a divisor instead of $(d^3-d)/2$?

David Gross Dec 17 2017 20:28 UTC

Nice observation, Steve! :-)

Steve Flammia Dec 17 2017 20:25 UTC

...(continued)The following observation resolves in the affirmative a decade-old open conjecture from this paper, except for $d=3$.

The Conjecture asks if any unitary 2-design must have cardinality at least $d^4 - d^2$, a value which is achievable by a Clifford group. This is true for any group unitary 2-design

Andrew W Simmons Dec 14 2017 11:40 UTC

Hi Māris, you might well be right! Stabiliser QM with more qubits, I think, is also a good candidate for further investigation to see if we can close the gap a bit more between the analytical upper bound and the example-based lower bound.

Planat Dec 14 2017 08:43 UTC

...(continued)Interesting work. You don't require that the polar space has to be symplectic. In ordinary quantum mechanics the commutation of n-qudit observables is ruled by a symplectic polar space. For two qubits, it is the generalized quadrangle GQ(2,2). Incidently, in https://arxiv.org/abs/1601.04865 this pro

Māris Ozols Dec 12 2017 19:41 UTC

$E_7$ also has some nice properties in this regard (in fact, it might be even better than $E_8$). See https://arxiv.org/abs/1009.1195.

Danial Dervovic Dec 10 2017 15:25 UTC

...(continued)Thank you for the insightful observations, Simon.

In response to the first point, there is a very short comment in the Discussion section to this effect. I felt an explicit dependence on $T$ as opposed to the diameter would make the implications of the result more clear. Namely, lifting can mix

Simon Apers Dec 09 2017 07:54 UTC

...(continued)Thanks for the comment, Simone. A couple of observations:

- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from ([arXiv:1705.08253][1]): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov

Simone Severini Dec 07 2017 02:51 UTC

...(continued)Closely related to

Simon Apers, Alain Sarlette, Francesco Ticozzi, Simulation of Quantum Walks and Fast Mixing with Classical Processes, https://scirate.com/arxiv/1712.01609

In my opinion, lifting is a good opportunity to put on a rigorous footing the relationship between classical and quantu

Mark Everitt Dec 05 2017 07:50 UTC

...(continued)Thank you for the helpful feedback.

Yes these are 14 pairs of graphs [This is an edit - I previously mistakenly posted that it was 7 pairs] that share the same equal angle slice. We have only just started looking at the properties of these graphs. Thank you for the link - that is a really useful r

Simone Severini Dec 05 2017 01:13 UTC

...(continued)When looking at matrix spectra as graph invariants, it is easy to see that the spectrum of the adjacency matrix or the Laplacian fails for 4 vertices. Also, the spectrum of the adjacency matrix together with the spectrum of the adjacency matrix of the complement fail for 7 vertices. So, the algorith

Mark Everitt Dec 04 2017 17:52 UTC

...(continued)Thank you for this - its the sort of feedback we were after.

We have found 14 examples of 8 node graphs (of the possible 12,346) that break our conjecture.

We are looking into this now to get some understanding and see if we can overcome this issue. We will check to see if the failure of our algo

Dave Bacon Dec 02 2017 00:08 UTC

...(continued)A couple of comments:

1. To be a complete algorithm I think you need to specify how many of the equal angles you need to sample from (i.e. how many Euler angles)? And also maybe what "experimental accuracy means"? If those are exponential in order to work that's bad (but still very interesting

Mark Everitt Nov 29 2017 22:13 UTC

...(continued)We received some questions from Jalex Stark. To paraphrase, they asked if we could check if our method can discriminate non-isomorphic graphs that are:

1. "quantum isomorphism" as defined in https://arxiv.org/pdf/1611.09837.pdf

2. isospectral

3. fractional isomorphic

4. C3 equivalenlent (

Zoltán Zimborás Nov 17 2017 07:59 UTC

Interesting title for a work on Mourre theory for Floquet Hamiltonians.

I wonder how this slipped through the prereview process in arXiv.

Aram Harrow Nov 07 2017 08:52 UTC

I am not sure, but the title is great.

Noon van der Silk Nov 07 2017 05:13 UTC

I'm not against this idea; but what's the point? Clearly it's to provide some benefit to efficient implementation of particular procedures in Quil, but it'd be nice to see some detail of that, and how this might matter outside of Quil.

Gui-Lu Long Nov 06 2017 20:23 UTC

great！

Noon van der Silk Nov 01 2017 21:51 UTC

This is an awesome paper; great work! :)

Xiaodong Qi Oct 25 2017 19:55 UTC

Paper source repository is here https://github.com/CQuIC/NanofiberPaper2014

Comments can be submitted as an issue in the repository. Thanks!

Siddhartha Das Oct 06 2017 03:18 UTC

Here is a work in related direction: "Unification of Bell, Leggett-Garg and Kochen-Specker inequalities: Hybrid spatio-temporal inequalities", Europhysics Letters 104, 60006 (2013), which may be relevant to the discussions in your paper. [https://arxiv.org/abs/1308.0270]

Bin Shi Oct 05 2017 00:07 UTC

Welcome to give the comments for this paper!

Martin Henessey Oct 03 2017 01:48 UTC

I am confortable with it. Good job

Martin Henessey Oct 03 2017 01:40 UTC

Well done

Bassam Helou Sep 22 2017 17:21 UTC

The initial version of the article does not adequately and clearly explain how certain equations demonstrate whether a particular interpretation of QM violates the no-signaling condition.

A revised and improved version is scheduled to appear on September 25.

James Wootton Sep 21 2017 05:41 UTC

What does this imply for https://scirate.com/arxiv/1608.00263? I'm guessing they still regard it as valid (it is ref [14]), but just too hard to implement for now.

Ben Criger Sep 08 2017 08:09 UTC

Oh look, there's another technique for decoding surface codes subject to X/Z correlated errors: https://scirate.com/arxiv/1709.02154