...(continued)The basic idea of this paper is to test whether the decimal digits of three special constants $(\pi,e,\sqrt2)$ act as though chosen from a uniform distribution, based on their first ten million digits. In particular the author studies the sum of the digits compared to the expected behavior by the la
...(continued)@rrtucci
The algorithm in your reference paper requires knowing in advance the exact number of marked items, represented by the quantity \gamma (to use your notation). The rotation angles (or phases) of the reflections depend on this quantity via equations (82) and (89) and is also explicitly state
Note: The arXiv reference in the abstract should be arXiv:1403.2362
...(continued)Dear Felix,
Thank you for your interest! Does the following answer your questions?
When discussing the equilibrium state associated with $R$, we are assuming that $R$ is quasiclassical. $\gamma_R$ has the form in your first set-off equation, $\gamma_R = e^{-\beta( H_R - \mu N_R)} / Z_R$. I
...(continued)Dear Nicole and Joe,
Very interesting paper! I have a question that is probably easily answered:
In the last paragraph of II.B, you state that each resource $R=(\rho,H,N)$ is associated with an equilibrium state $G = (g_R,H,N)$. I'm not sure how $g_R$ is defined. If $R=(\rho,H_R,N_R)$ and $S=(\sig
...(continued)Thank you for your comment. In Jordan-Shor paper, they say DQCk_1 and DQC1_1 belong to the same complexity class in the sense that both can approximate the trace of an n×n unitary operator with an "additive" error $2^n / \text{poly}(n)$. However, DQCk_1 is not equivalent to DQC1_1 if one consider it
...(continued)I think this hardness result for DQC2$_1$ combined with the fact that DQC$k_1$=DQC1$_1$ (for constant $k$ pure qubits) as shown in the Jordan-Shor reference already yields hardness for DQC1. As this answers the original question on the simulability of DQC1, I would suggest to the authors to include
For those interested in a proposal for an experimental implementation of protocols in the DQCk_{m} 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.
We have applied our Research work on various servers, NGIX performs better, VPS Hosting Godadday servers Representative for [explorequotes][1] working fine, finally we have concluded that all the experiments were satisfactory
[1]: http://explorequotes.com/
...(continued)The argument in the paper "Critique of Feinstein's Proof that P is not equal to NP" has a straw man fallacy. Never in Feinstein's paper does he claim, "...This is because we have a non-polynomial time reduction from SUBSET-SUM to FIND-RECORD...", as the authors claim he does on page 4 of their paper
This algorithm is from Wu's list decoding algorithm.
...(continued)Thanks Dr. Hastings for your comment. It is true that the transverse field Ising model does not satisfy the requirements to apply our method with an exponential reduction. Indeed, the opposite would be quite impressive since the random Ising model is a NP-Hard problem and we ourselves would be prett
The "quite general" conditions seem not to include the transverse field Ising model, the subject of most of the intensive numerical work previously. Incidentally, the terms "Lanczos" and "Krylov subspace" might be helpful.
...(continued)I take the database search problem addressed by Grover to be the problem of given an n-ary Boolean function which takes the value of 1 on a designated one of the $2^{n}$ possible inputs (representing a designated record in a database with $2^{n}$ records) and 0 elsewhere, to find the input values fo
...(continued)I agree with the bottom line of your assesment, but disagree with your analysis.
Quantum computing is obviously motivated by physics. But there is no reason (on the level at which you take nondeterministic Turing machines seriously as a "model of computation") why you couldn't consider models of
...(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.
Braneshop, and
the US National Science Foundation.
SciRate