10

Are there examples of quantum algorithms only composed of Clifford operations that show [...] A reduction in the "same spirit" of the $n^{800}→n$ for instance. No. An $n$ qubit Clifford+measure circuit with $m$ operations can be simulated in $O(n^2m)$ time (arXiv:quant-ph/0406196) with small constant factors (arXiv:2103.02202).


8

"but for me quantum supremacy would mean that no classical algorithm can exist at all that solves the problem in a better way than a quantum algorithm." If that were the case, then "quantum supremacy" would almost not exist at all. Even Shor's algorithm for factoring numbers in polynomial time would not be considered "superior" ...


6

I am not an expert in the field but there are a few points that I am aware of: There are proofs that certain quantum machine learning algorithms cannot be efficiently simulated on a classical computer even if the classical computer has analagous sampling access to the data as the quantum algorithm does (i.e. they cannot be dequantized) [1-3]. However there ...


6

Quantum advantage using Clifford gates Gottesman-Knill theorem applies to stabilizer circuits only, not to all circuits consisting of Clifford gates. The former satisfy the stronger requirements of having a stabilizer input state and using only stabilizer basis measurements. Note that availability of magic states enables one to apply non-Clifford gates using ...


5

"As far as I understand there aren't many rigorous results on performance of these algorithms, similar to many classic machine learning approaches." You are correct in that, unlike Grover's algorithm where we can prove that a search that would cost $\mathcal{O}(N)$ on a classical computer can be done with only $\mathcal{O}(\sqrt{N})$ on a quantum ...


4

To study unitary $t$-designs, we define the moment operator with respect to a probability measure $\nu$ as $$ M_t(\nu) := \int_{U(d)} U^{\otimes t} (\cdot) (U^{\otimes t})^\dagger d\nu(U) \simeq \int_{U(d)} (U \otimes \bar U)^{\otimes t} d\nu(U). $$ Often, designs are defined via subsets $D\subset U(d)$ endowed with some "canonical" measure. For ...


4

The issue that easily leads to confusion is the dual role played by output bitstring probability. It enters the computation of the average in two ways. On one hand, it determines how often one sees different bitstrings. On the other hand, it determines the contribution that each bitstring makes towards the average. In mathematical terms, the output bitstring ...


4

I am going to answer your question as you phrased it in the comments: "I am asking if you can give me an example of classical code (that is not parallelizable) that can be sped up by a quantum computer" where, as I understand you, "not parallelizable" means that we have no idea how to parallelize it. Specifically, it is known that ...


3

Partial answer (why qRAM is useful) Currently, quantum computers do not have an operational memory. Quantum processor is composed of qubits which can be considered to be an elementary memory. However, they are rather used for performing calculations. There is no way how to save intermediate results. Of course, you can measure an output of the quantum ...


3

First of all, that does not imply anything for shorter (constant/logarithmic) depths. Moreover, the 2-design property does not imply that the outcome distribution is the same as for Haar-random unitaries, but only the first and second moment is. In the mentioned paper, they consider anti-concentration of the outcome distribution. To show this feature, a ...


3

Maybe think of it this way - a quantum computer, executing a small enough random circuit $C$ acting on a state initially prepared as $\vert 0^n\rangle$ and sampling therefrom, will get an $n$-bit string as output, say $0110\cdots10$. We know, merely from the fact that this was sampled, that the squared amplitude of $\vert 0110\cdots10\rangle$ is large and ...


3

(3) is a solid objection. I'm not sure what specifically is meant by "number of variables within a problem that a quantum technology can optimize" but we can use the results of [1] (Fig 4) test some interpretations. In that experiment, QAOA was implemented on a nearest-neighbor connectivity superconducting processor to solve 3-regular MaxCut. If ...


3

Yes - you can use Grover search to speed up finding an element $x$ which satisfies $x=f(x)$. It is clear that for an unstructured function, this cannot be done faster than by $O(N)$ queries classically, and it is also clear that this can be solved using Grover search in $O(\sqrt N)$ steps. On the other hand, for an unstructured function $x$ I'd argue that ...


3

The paper does not specify the exact algorithm or class of distributions $\mathcal{D}$ for which such algorithm fails to refute XQUATH, and some classes of distributions $\mathcal{D}$ do not satisfy XQUATH, so some additional assumptions about $\mathcal{D}$ are needed. In this answer we will try to follow the idea of the paper and try to show that it fails ...


3

I believe so (caveat: this is not something I've every thought about before). I'm going to rewrite the $p_x$ from your question as $p_{xy}$. So, we have $$ p_{xy}=|\langle x|U_1|0^n\rangle|^2\ |\langle y|U_2|0^n\rangle|^2 $$ Note that this is two independent probabilities $p_x$ and $p_y$. Now, the probability that $p_{xy}>\alpha'$, which we write as $\...


2

Your intuition is correct if you think of the superpositions as classical probability distributions, which is how they are usually described in popularizations. What's unique to quantum mechanics is not superposition as such, but constructive/destructive interference between different computational paths, which leads to certain results appearing more/less ...


2

In the absence of additional assumptions, $\mathbb{E}[p_i]$ can be any real number in $[0, 1]$. For example, let $a\in[0,1]$ and define the POVM as $M_0=aI$ and $M_1=(1-a)I$. Then $$ \mathbb{E}[p_0] = \int \mathrm{tr}\left(aI|\psi\rangle\langle\psi|\right)d\psi = a \int \langle\psi|\psi\rangle d\psi = a $$ assuming the Haar measure is normalized. Similarly, ...


2

The commuting model only differs from the spatial (tensor-product) model when one considers infinite-dimensional Hilbert spaces, so one would have to start with considering circuits with an infinite number of degrees of freedom. That being said, such a model has been considered in this paper and is called the $C^*$-circuit model.


2

Calculating $\rho_1$ Let $N=2^n$ denote the dimension of the Hilbert space where $|\psi\rangle$ lives. For $i=0,\dots,N-1$, let $V_i$ be any unitary that maps $|i\rangle$ to $|0\rangle$. The action of $V_i$ on other computational basis states $|j\rangle$ with $j\ne i$ is irrelevant. Exploiting the invariance of the Haar measure to absorb $V_i$ into the ...


2

I think your hierarchy collapses, or at least would never get beyond $P$, following the top-line results of Bravyi and Gosset. Bravyi and Gosset's paper gives an algorithm to classically simulate a quantum circuit on $n$ qubits comprising $O(\mathrm{poly\:}n)$ Clifford gates and a constant number of $T$ gates - that is, polynomial in $n$ (although ...


2

Grover's algorithm has two components, which alternate and repeat $O(\sqrt{N})$ times: a diffusion operator and an oracle operator. The diffusion operator will cause problems with your idea. As I understand, what you want to do is start from a uniform superposition $$\vert \psi_0\rangle =\frac{1}{\sqrt{2^n}}\sum_{b_1,\dots,b_n\in\{0,1\}} \vert b_1\rangle \...


2

I think the key issue here is interference from the elements in the superposition. If you do not have interference, you do not get any speedup, just a probabilistic classical algorithm.


2

The two facts are connected in that they both arise as a result of rotational invariance of the Haar measure. We will derive them in the case of large $n$ since this is when the Porter-Thomas distribution takes the exponential form given in the question. Also, this case admits an intuitive proof backed by a geometric picture. For small $n$, Porter-Thomas ...


2

I think your best bet as of now is to derive such a table from the Quantum Algorithm Zoo, which, as you mention although partly dated, would serve as a good starting point but would require reading between the lines. For example, the Zoo mentions a speedup in solving exponential congruences of $\tilde{O}(q^{3/8})$ quantum, but a $\tilde{O}(q^{9/8})$ ...


2

A Grover algorithm outperform classical unordered database search algorithms quadratically. So, it can serve as an example of higher performance of quantum computers. However, when complexity of Grover search is assessed, generally a complexity of an oracle is ignored. In some cases the oracle complexity is so high that it cancels out advantage of faster ...


2

Both VQE and classical methods rely on the variational principle. The variational principle for quantum mechanics says that if you have a physical system $H$ and a wavefunction $|\psi\rangle$ describing a state in that system, it's expectation value $\langle \psi | H | \psi \rangle$ will be greater than the ground state energy, $E_0$. In other words, you can'...


2

Quantum computing is not a tool to be used for general purpose computing. In general for most common computer programs quantum computing, even on a perfect machine, would provide little advantage over a CPU. In these programs there is no need to use quantum features such as entanglement. May be you could run programs more efficiently, but then it makes more ...


2

I can see what you mean. For the Deutsch problem, we can formulate it (or think of it) in such a way that the goal is to evaluate $f(0)+f(1)$ in base 2. Classically we have to evaluate $f(0)$ and $f(1)$ to get this sum, so we need to do two evaluations of the function to get the answer. A quantum computer only needs to input the superposition state $\frac{1}{...


2

Note that the quoted relation $$ \bar M_i = \sum_\lambda a_\lambda P_\lambda, $$ only holds if the $M_i$ also commute with the representation of the symmetric group! Otherwise this can obviously not be true by a simple counting argument: The dimension of the commutant $U\mapsto U^{\otimes n}$ is $n!$ but there are certainly less partitions of $n$. Thus, the ...


2

We use the Haar measure, thus for any unitary $U_0$ the distributions of $U$ and $UU_0$ are the same. Hence, the distributions of $|\psi\rangle = U|0^n\rangle$ and $|\psi\rangle = UU_0|0^n\rangle$ are also the same. Therefore, it's the same distribution $|\psi\rangle = U|\psi_0\rangle$ for any state $|\psi_0\rangle$. So, the standard basis plays absolutely ...


Only top voted, non community-wiki answers of a minimum length are eligible