Recent comments from SciRate

### Reviewer 1 ###

The main topic of study is the zero-error capacity of a classical communication system with a noisy classical channel, complemented with side information passing via a perfect noiseless quantum channel, in the form of shared entanglement between sender and receiver.

The math

...(continued)

### Reviewer 1 ###

This paper is about a parallel repetition theorem for particular non-signaling games involving multiple players. The work generalizes recent results on parallel repetition theorems for two-player games to the multiplayer case. The proofs are nontrivial and the approaches are

...(continued)

### Reviewer 1 ###

The paper considers the communication complexity of the following sampling problem: n classical, cooperating players are each given a description of a single-qubit projective measurement, and they must produce a joint distribution of output bits that is equal to the distribut

...(continued)

### Reviewer 1 ###

This paper deals with a method to certify rates of randomness generation in a random generator device that is based on shared entanglement between two parties A and B. This method allows to certify more randomness than previous methods, which only use the amount of violation

...(continued)

It'd be interesting to see if the results change at all by targeting groups based around subjects other than software development. I'd expect developers to have non-representative knowledge of and interactions with bots.

Hi mick,

Just to make my notation clear.

The requirement in page 2 is what we call a "strong simulation". They have been studied in the literature. Indeed we know that simulating universal Q computers strongly is **#P-hard**. (But this paper studies the case for the **DQC1** model.)

Adopting the

...(continued)

I think that Matt and Keisuke were already gently pointing this out, but the authors have assumed in their proof that **#P** is inside **P**, which would certainly imply that **BQP** is inside **BPP** as it has long been established that **#P** is an upper bound on **BQP** (if one allows the right k

...(continued)

I consider the last sentence of the abstract little ambitious. The local structure of the problem, as defined in the paper, has not been analyzed. The structure is very important as it has to be mapped onto the Chimera architecture of the D-Wave machine. The mapping itself might not be trivial and r

...(continued)

As far as I understand the paper, I think that the main result is that the **DQC1** model is *as hard to simulate as* universal quantum computers if one adopts the notion of *strong classical simulation*: given a quantum circuit, input state, final measurement, one is asked to compute the probabili

...(continued)

Strong simulation of an output probability distribution is much harder than what quantum computer actually does as in Ref http://arxiv.org/abs/0811.0898, where strong simulation of a certain task is shown to be #P-hard, while weak simulation (sampling) of it can still be efficiently simulated.

For those interested in a proposal for an experimental implementation of protocols in the one clean qubit model, please see http://iopscience.iop.org/1367-2630/16/5/053045/article?fromSearchPage=true . It is experimentally feasible and could operate in very large Hilbert spaces.

This does seem to be a rather strong notion of approximation (to within exponential accuracy).

It's a bit funny to look at a formally verified proof of the CLT :), here it is online:
https://github.com/avigad/isabelle.

There's a nice summary of the context for this paper here: http://fioraaeterna.tumblr.com/post/56556056152/quasistars-a-real-life-black-hole-sun

This is not new. The same measure has been defined here: http://arxiv.org/abs/1309.1472

I am confused about the last paragraph of the section 2. To my knowledge Cleve et. al introduced the CHSH game. Clause et. al introduced only the inequality.

+1 to MB

Or "Alan" and "Barbara", and then we have both Turing and a Turing Award recipient.

Independently, those of us who still use "Alice" and "Bob" could agree on replacing "Eve" (which has never been gender neutral) by "Elsevier".

It would have been nice if a measurement of randomness were presented.

By now someone should have told Yuen that Adam and Babe is sexist.

Why not Adam and Barbara?

"Adam" and "Babe" have been featured in previous papers of Horace Yuen.

One would think that repeating an old argument does not make it righter ;-) But at least this edition introduces Adam and Babe, an interesting variation on Alice and Bob.

Dear Jaeyoon,

This is a very nice result. Condition 1 is reminiscent of the Local-TQO condition necessary for stability of frustration-free gapped Hamiltonians (see Corollary 3 and 4 in http://arxiv.org/abs/1109.1588). Local-TQO is supposed to be generic (see Section VI in http://arxiv.org/1306.4

...(continued)

A podcast summarizing this paper, by Geoff Engelstein: [The Dice Tower # 351 - Dealing with the Mockers (43:55 - 50:36)](http://dicetower.coolstuffinc.com/tdt-351-dealing-with-the-mockers), and [an alternative link on the BoardGameGeek](http://boardgamegeek.com/boardgamepodcastepisode/117163/tdt-351

...(continued)

Glad the coarse-graining is clear now. Regarding separating out a qubit, my claim is not just that if sites 1,N are in a pure state one can separate out a qubit. I also claim that even if sites 1,N are in a mixed state of the form $\sum_{\text{correctable errors} E_1 \text{and} E_2} p(E_1,E_2) E_1

...(continued)

Thanks for clearing things up about the definition of coarse-graining; I guess I thought the name suggested some kind of real-space renormalization.

About separating out a qubit: I wrote that one expects "the result to be close to a mixed state like $∑_{\text{correctable errors } E_1 \text{ and }

...(continued)

Hi Ari, let me reply to your second point first, since I think there may be a misunderstanding about "coarse-graining". If we mistakenly treated the polylog chains as a single spin-1/2 chain, this would give an incorrect result, but I certainly did not suggest doing anything like that. Instead,if

...(continued)

Matt, I still take issue with the coarse-graining approach.

1) You wrote "When we say "close to maximal entanglement", we mean we can separate out a qubit from coarse-grained spin 1 and a qubit from coarse-grained spin N (let me stick to my notation) and those two qubits are close to maximally enta

...(continued)

One can indeed always ask this coarse-graining question, and one important issue is how strong the resulting interactions are. The coarse-graining itself is definitely well-defined, the question is whether one correctly treats the resulting 1d system. In this case, there is a variational argument

...(continued)

You raise an interesting question. It can perhaps be simplified slightly by imagining a quantum circuit that initializes 2 qubits to |0>, generates an EPR pair between qubits 1 and 2, then applies N-1 identity gates to qubit 2. The circuit can be turned into a fault-tolerant version of itself, and

...(continued)

I am curious about the following setting. Consider a quantum circuit that initializes N qubits to |0>, then generates an EPR pair in qubits 1 and 2, and then applies SWAPs to move the qubit from 2 to 3 to 4 to ... to N, leaving ultimately an EPR pair between 1 and N. This can be turned into some f

...(continued)

Ryan is exactly correct. The method would work with any of the clock constructions, however we decided that the machinery they developed to make sure it was implementable in qubits was unnecessary overhead for a classical implementation, where having a qudit with large d does not present a great ch

...(continued)

Thanks for the remark, Steve. I do not have additional numerics, but I don't think that the translational invariance plays an important role in the spin-wave form of the excitations. I think that the local excitations approximately satisfy a tight-binding Hamiltonian with hopping between adjacent

...(continued)

Thanks for raising the issue, Aram. I think that Matt gave a good answer.

Reference [26] is just cited for the definition of the local stochastic fault model. Reference [25] is the relevant one for the issue you mention. I am confused as to why you say that reference [25] uses measurement. Th

...(continued)

Thanks for the comments, Matt. I am sincerely happy to hear about points that need clarification.

Thanks for the comments, Dave! Hope you are enjoying life at Google.

The "local stochastic excitation" error model is mathematically natural for the construction in the paper. Fault-tolerance against this error model is inherited immediately from the fault-tolerance of the standard gate model. (

...(continued)

I'm concerned that the spin-wave ansatz will fail to give a good approximation of the excitations as soon as the Hamiltonian is no longer translation invariant. If I understand correctly, the numerics were done for the T.I. case only. Does the author have non-T.I. numerics as well that support the s

...(continued)

Aram, I believe that the idea is to use the ability to initialize new qubits to a given state partway through the computation to make up for the absence of measurement. Note that in the usual circuit approach with faults, a qubit that is "idle" will still have faults applied to it at each time step

...(continued)

I am very worried about these sentences towards the top of page 3:

> Consider a quantum circuit C,...
> Assume that C involves no measurements and that C is fault-tolerant
> [25] against a local stochastic fault model [26].

We have known for a [long time][1] that FTQC requires either measuri

...(continued)

Great to see Ari continue to tackle this problem (I spent many wonderful hours with arxiv:1002.0846).

After reading this over a few times, I have a few questions about the first error model the paper considers. My understanding of this error model is as follows. Start with a fault-tolerant circ

...(continued)

Maybe I should not bring political issues here, but the saddest thing here is the affiliation:

> Ward 350 of Evin Prison, Tehran, Iran

Read more on Wikipedia: [Omid Kokabee](http://en.wikipedia.org/wiki/Omid_Kokabee).

I'll let Jarrod correct me if he disagrees but I think the point Jarrod is making is that the original clocks of Feynman and Kitaev were designed with physical implementation in mind whereas this proposal is for a classical algorithm and as such, should not be measured by the same considerations (su

...(continued)

This is a significantly revised version of our paper.

The previous version titled ***Finding is as easy as detecting for quantum walks*** had a very subtle mistake, so the updated result is slightly weaker: it holds only for a single marked element. The updated version includes much more details

...(continued)

Jarrod,

Would there be any issue if you had used the original Feynman's clock or Kitaev's clock for simulating quantum systems classically?

Thank you for your quick reply. In that case, as long as we are using qubits for your scheme we should be good. Having said that I am afraid it may jeopardize the local structure recommended by Feynman to some extent.

Thank you for your interest in our paper! The reason for the apparent discrepancy is that our paper is designed for classical simulation of quantum systems using ideas (namely Feynman's Clock) from quantum computation. When performing the simulation on a classical computer, the underlying qubit st

...(continued)

In equation 7 of the paper, the clock register is different from Feynman's original proposal. According to this paper, for a four clock steps quantum circuit, the sequence of the state of the clock register will be $|00\rangle \to |01\rangle \to |10\rangle \to |11\rangle$. It infers that we will nee

...(continued)

It seems to me that for the architecture you propose, loss is a much more worrisome source of error than you make it appear in the paper. For example, in the paper by Rhode and Ralph that discusses sources of error in Boson Sampling, it is argued (roughly) that the interferometer may still be hard t

...(continued)

Is this the first experiment which uses the Eberhard inequality?

In the second version, all missing pieces of the first version are proven, and an explicit construction of the adversary matrix for the collision and the set equality problems is given.

I enjoyed reading this paper, which makes an interesting connection between quantum state preparation and Bayesian network; the latter is something I am not familiar with. Although this paper is well written, there is some overlap with the existing literature not covered, in particular the problem o

...(continued)