...(continued)You might understand why I thought that you were trying to say something about quantum computing (e.g. Grover's algorithm) over $\mathbb C$, from the following excerpts:
(*from the abstract*)
> Indeed, our analysis of the transparent calculations of Boolean functions over $\mathbb Z/2$ shows tha
...(continued)I guess the reason why people use $\mathbb{C}$ instead of $\mathbb{Z}_2$ is because this is what comes from the Schrodinger equation. The reason why counting function evaluations is considered a plausible measure of complexity is that if you have a way of computing a function using X oracle calls a
...(continued)Niel de Beaudrap's comments on my paper [arXiv:1407.4345][1] misrepresent it in a number of respects and seem more designed to plug his own work. I am of course familiar with the work of my friend Amr Sabry with various coauthors and that work is cited in an earlier paper on quantum mechanics over $
...(continued)I would not normally comment on such an article, but this one touches on a topic which I think has potential for obtaining complexity-theoretic results: quantum-like computing over distributions in which $\mathbb C$ is replaced by an arbitrary ring. I would not like for this article to be considered
...(continued)Dear Spiros,
Thank you very much for your generous comments and please forgive me for a terribly late reply.
Your remark on the local-TQO is very interesting. Let me first clarify that the condition (1) alone does not tell you anything about the internal structure of the ground state. It merel
...(continued)In the last paragraph of the first column of page 3 says,
> This space contains $2^{NU}$ strings, and we have just send that $N!$
> of these strings $p_\pi$ encode permutations $\pi$.I have following confusions.
- First of all, $\pi$ is a single definite permutation. So the sentence says
I think I know what is going on there. $\pi_{i,j}$ is just 0 or 1 and will be the corresponding digit of the binary representation of $\pi_i$.
I am little confused about equation 3 on page 3. It is,
$\pi_i=\sum^{U-1}_{j = 0} \pi_{i,j}(2)^j$
I have no clue what $\pi_{i, j}$ is. Any idea from anyone? Let $\pi_i = 3$ and $U = 2$. What should be the values of $\pi_{i,0}$ and $\pi_{i,1}$?
...(continued)I'd like to thank the anonymous reviewers, and address their comments with the following remarks.
I agree that it is fairly straightforward to observe that the quantum coding schemes of Refs. [[17](http://www.arXiv.org/abs/0908.1457), [18](http://www.arXiv.org/abs/1012.4583)] are realisable as meas
...(continued)I'd like to thank the anonymous reviewers for the time spent preparing their feedback. I would like to address their remarks, as follows.
* Reviewer #1 says: "This implies that the ground space is spanned by product states, so one may wonder whether there is anything quantum left about the problem
...(continued)This is a neat result, but it does not deliver on the promise of the
title and abstract. The key point is the assumption (ii) made on top
of p.2, which states, roughly speaking, that $A_1\otimes A_1$ is
compatible with $A_2\otimes A_2$. Although this assumption indeed
holds for the typical qua
...(continued)This paper has been published in the IEEE Transactions on Information Theory without any peer review. It is unfortunate that this has happened. The story is that I was requested to review this paper in late 2010, and I returned my report within 2 months of receiving the request. From what I can tell
...(continued)[Carl Linnaeus](http://en.wikipedia.org/wiki/Carl_Linnaeus) appears to benefit a lot from this particular algorithm (and perhaps any other taking all links with the same value). Just look at [inbound links](http://en.wikipedia.org/wiki/Special:WhatLinksHere/Carl_Linnaeus) - vast majority of them ref
...(continued)### Reviewer 1 ###
I like the ideas in this manuscript. It is not clear to me how novel it is in view of Ref. [17] and [18], but is certainly worth presenting.
I found it difficult to read and some of the notation confusing. For example, the decomposition in Fig. 3 does not look at all like
...(continued)### Reviewer 1 ###
The paper investigates a generalization of the notion of quantum colorings, and their associated nonlocal games, to graph homomorphisms.
A homomorphism from a graph $X$ to a graph $Y$ is a mapping $f$ from the vertices of $X$ to the vertices of $Y$ that preserves edge relat
...(continued)### Reviewer 1 ###
This paper discusses Device-Independent Randomness Extraction.
As a criterion for randomness extraction, it adopts Eqs.(1) and (2), which consider the min entropy of each bit conditioned on the other bits and Eve's information.
I am slightly puzzled by this criterion,
...(continued)### Reviewer 1 ###
The Authors consider the problem of verification of a quantum computation for cases in which only a limited subset of quantum computation is available. In particular, they consider the class of quantum computation with one pure qubit (DQC1) and ask how one can verify whethe
...(continued)### Reviewer 1 ###
Summary of Result:
This submission studies a new notion called “partial-indistinguishability” in the context of circuit obfuscation and provides two instantiations of obfuscators (satisfying the new notion) of classical and quantum circuits respectively. Moreover, the constr
...(continued)### Reviewer 1 ###
This paper studies the complexity of random instances of the counting problem #2-QSAT, which is (roughly speaking) the task of determining the degeneracy of the ground space of a 2-local qubit Hamiltonian. Here "random" means that the interaction graph is random in some way
...(continued)### Reviewer 1 ###
This submission discusses several new properties of the newly discovered quantum / sandwiched Renyi divergence, with applications to channel coding and hypothesis testing. These new relations might very well prove useful for other applications in addition to the ones given here
...(continued)### Reviewer 1 ###
A random access code (RAC) is a concise encoding of a bit-string such that any individual bit of the string can be retrieved (with good probability). This paper studies a variant of RACs -- parity-oblivious RACs, or PO-RACs -- where in addition the code has the cryptographic
...(continued)### Reviewer 1 ###
This paper uses the formalism of Cabello, Severini, and Winter for associating projective measurements on quantum systems with graphs to study the entangled value of non-local games. They show several very interesting results in this regard. In particular, that the Lovasz theta
...(continued)### Reviewer 1 ###
This paper shows that the strong converse of the quantum capacity of the erasure channel holds for almost all codes under the Haar measure.
The result is interesting and seems correct. Since the topic is challenging, I can recommend to accept this paper. However, I have seve
...(continued)### 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
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.
...(continued)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
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.
...(continued)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
Braneshop, and
the US National Science Foundation.
SciRate