18

The term quantum supremacy doesn't necessarily mean that one can run algorithms, as such, on a quantum computer that are impractical to run on a classical computer. It just means that a quantum computer can do something that a classical computer will find difficult to simulate. You might ask (and rightly so) what I might possibly mean by talking about ...


17

It's just a coincidence. I can speak from personal recollection on the Google side. Google originally intended to use a 72 qubit chip (Bristlecone) where qubits were essentially directly connected to each other. They then switched to an architecture where qubits were connected indirectly via a coupler. The coupler requires a control line, so this increased ...


15

There are several countries that are actively participating in the "Quantum Race", most of which are making significant investments. The estimated annual spending on non-classified quantum-technology research in 2015 broke down like this: United States (360 €m) China (220 €m) Germany (120 €m) Britain (105 €m) Canada (100 €m) Australia (75 €m) Switzerland (...


15

Google's paper/results are kind of sideways to questions in computational complexity about the relation between $\mathrm{BPP}$ and $\mathrm{BQP}$ (and even further from questions about whether $\mathrm{P}\ne\mathrm{NP}$). It's more as if Google relies on the hypothesis that $\mathrm{BPP}\ne\mathrm{BQP}$ as evidence that their quantum computer performs a ...


13

There are a continuous set of possible states for $n$ qubits, each of which can be expressed as a superposition of the $2^n$ basis states. Mostly of these states are highly entangled, and would require highly complex circuits to create (assuming the standard gate set of single qubit rotations and two or three qubit entangling gates). These circuits would ...


12

Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is more or less nonexistent...), but a recent result by Bravyi et. al presented a class of '2D Hidden Linear Function problems' that provably use fewer resources on a quantum ...


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).


9

For all we know, it is extraordinarily hard to prove that a problem which can be solved by a quantum computer is classically hard. The reason is that this would solve an important and long-standing open problem in complexity theory, namely whether PSPACE is larger than P. Specifically, any problem which can be solved by a quantum computer in polynomial ...


9

"What feature of a quantum algorithm makes it better than its classical counterpart?" First, a classical algorithm can be thought of as a quantum algorithm that makes no use of quantum superpositions. Therefore a quantum algorithm can be at least as good as its classical counterpart. No classical algorithm can be "better" than quantum ...


9

TL;DR: While two qubits must be transmitted in total, in the instant where two bits are to be communicated, only one qubit has to be sent. The information being sent is masked, but it is not truly secure. There are two distinct phases to a superdense coding protocol. In phase 1, Alice and Bob prepare a Bell state $(|00\rangle+|11\rangle)/\sqrt{2}$. This is ...


9

Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is the only solution, this means $f$ is 1-to-1; otherwise there is a nonzero $s$ such that $f(x) = f(x + s)$ for all $x$, which, because $2 = 0$, means $f$ is 2-to-...


8

TL/DR: The two-qubit gates are going by the moniker "Sycamore gates" in the paper, and it appears that they would ideally want to explore more of the $(\phi, \theta)$ phase-space but for their purposes (of quantum supremacy) their current Sycamore gate is sufficient. The pattern of gates $\mathrm{ABCDCDAB}$ was chosen to avoid "wedges" ...


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" ...


7

The term quantum supremacy, as introduced by Preskill in 2012 (1203.5813), can be defined by the following sentence: We therefore hope to hasten the onset of the era of quantum supremacy, when we will be able to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers. Or, as wikipedia rephrases ...


7

The complexity class of decision problems efficiently solvable on a classical computer is called BPP (or P, if you don't allow randomness, but these are suspected to be equal anyway). The class of problems efficiently solvable on a quantum computer is called BQP. If a problem exists for which a quantum computer provides an exponential speedup, then this ...


7

What does "obtaining samples" mean in this context? The same thing it means in a more classical context. Consider the probability distribution of the possible outcomes of a (possibly biased) coin flip. Sampling from this probability distributions means to flip the coin once and record the result (head or tail). If you sample many times, you can retrieve ...


7

They say in Section X.H of the supplement that the Summit supercomputer has a power capacity of 14 megawatts. They compare that to their own setup. Their power consumption is mainly their dilution fridge, which they say is about 10 kilowatts plus about another 10 for chilled water for its supporting equipment. Their own supporting PCs and other ...


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

How do we know no better classical algorithm exist? We can know thanks to computational complexity theory, which studies the complexity of solving different problems with different computational models. It is in principle possible to prove that no classical algorithm can solve a given problem efficiently. A common way to do it is using reductions, that is, ...


6

The problem is with your initial assumption: the oracle for Grover's is based on a function f(value)=0/1, where 1 indicates that the value meets your search criteria and 0 indicates that it doesn't. This means that you do have to build a new oracle for each different search, but not for each different database. That said, Grover's algorithm and a quantum ...


6

You are right to recognize the complexity of building the oracle to use it with Grover's search - it is indeed the tricky part of solving the problem, and indeed a lot of sources don't consider this complexity. I like to think about the oracle as a tool to recognize the answer, not to find it. For example, if you're looking to solve a SAT problem, the ...


6

There are a couple variants of the HOG test. "Old HOG" computed the proportion of unique samples whose probability is larger than the median probability of the distribution. It then compares that proportion to a threshold, e.g. 2/3. If you have enough larger-than-median outputs, you pass the test. "New HOG" instead computes the mean of the probabilities of ...


6

1 and 2 have elements of truth, but are only partially correct, with big caveats. 3 and 5 are complete nonsense. You can choose to read 4 the right way to make some sense out of it, but it doesn’t contribute to the computational speed of any algorithms.


6

While Craig Gidney (from Google) is correct in his comment which says that $X$ and $Y$ do not create superpositions on states that are not in superposition, such as $|0\rangle$ and $|1\rangle$; even if we assume that the initial state must not be in superposition, it is still possible to create superpositions with the 2-qubit gates, even if the 1-qubit gates ...


6

As so often, and especially in young research areas, the answer depends quite a lot on how you break down the question. Let me try a few examples: Does quantum mechanics change what is theoretically learnable? A beautiful paper is this reference which states a few complex results in rather clear words. Again, it depends very much on what you define as "...


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

Grover's algorithm does not have an advantage when searching an unordered database, because encoding the oracle into a circuit requires $\tilde \Omega(n)$ operations. You can prove this with a simple circuit counting argument. If the circuit had size $O(n^{0.99})$ then there would be fewer distinct circuits than distinct oracles. So the actual operational ...


5

You are correct that solving Sudoku for $n^2 \times n^2$ grids with $n\times n$ blocks is an NP complete problem. The quantum complexity class BQP is the class of decision problems solvable by a quantum computer in polynomial time (with an error probability of at most 1/3 in all cases). The relationship between BQP and the classical complexity classes P and ...


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

While a follow-up question asks for the motivation behind the two-qubit gates used in Sycamore, this question focuses on the random nature of the single qubit operations used in Sycamore, that is, the gates $\{\sqrt{X},\sqrt{Y},\sqrt{W}=(X+Y)/\sqrt{2}\}$ applied to each of the $53$ qubits between each of the two-qubit gates. Although I agree with @Marsl ...


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