16

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


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


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

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


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


7

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


6

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


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


5

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


5

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


5

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


5

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


4

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" and maximize/optimize ...


4

Actually, after having researched the question over the last months, the two answers (one above and one below) are correct, but we can build upon them to get something more up to date. The first answer, however, relies on figures and data which are slightly obsolete, while the source is uncertain (it is impossible to know if the source is McKinsey or The ...


3

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


3

None. The quantum race is lead by those entities capable of building the most powerful quantum computer and it are enterprises like IBM, Google, Intel, Microsoft, D-Wave that are currently building the most powerful quantum computers. So it are enterprises that are leading this race and not countries.


2

Whilst I cannot supply a formal proof, the simulation of (the temporal evolution) of a quantum system is believed to be such a case: There is no known better way to do this on a classical computer than in exponential time but a quantum computer can trivially do it in polynomial time. The idea of such a quantum simulator (see also wikipedia article) is in ...


2

A Different Way Of Looking At Linear Algebra Tensor Networks provide a different way of looking at linear algebra particularly within the context of tensor space systems. Quantum Circuits Are Just Products of Vectors and Operators A quantum circuit is inherently a tensor space system as when we have multiple qubits we must think of the whole circuit with ...


2

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


2

This answer only addresses the part about the necessity of the randomness of the circuit because I am by no means familiar with the physical implementation of the qubits at Google and what kind of constraints these impose on the implementation of certain gates. Now, for the randomness: Consider the problem of sampling from the output distribution of a ...


2

Generally speaking, to prove quantum supremacy, you don't need to sample several times from the same unitary/circuit/output probability distribution. If you extract even a single sample from the output probability distribution of a circuit which you know is extremely hard to simulate classically, then you already achieved something that you couldn't do (...


2

In the Sycamore paper linked in the comments, in the description of FIG. 4, the authors state: ...For each $n$, each instance is sampled with $N_s$ between 0.5 M and 2.5 M... For $m=20$, obtaining 1M samples on the quantum processor takes 200 seconds, while an equal fidelity classical sampling would take 10,000 years on 1M cores, and verifying the fidelity ...


2

As an initial matter, I think the Supplementary Information (linked in some other answers on this sight) has a significant amount of discussion on $\mathcal{F}_{XEB}$. However, as I understand it (misunderstandings are my own): There is indeed a concentration of outputs from a random quantum circuit, away from a state wherein the square of the coefficients ...


1

I think the rough, imprecise answer is "yes, $20$ cycles of the one- and 2-qubit gates of Sycamore is sufficient to be able to generate a (Haar measure)-random element of the Hilbert space of dimension $2^{53}$." For example, the diameter (longest shortest path) between any two qubits on Sycamore is $12\lt 20$, thus any two qubits should have a chance to ...


1

Remember that quantum computers contain, as a subset, the classical logic gates. So your assertion that "classical computer are way better at doing arithmetic operations" is not entirely clear. Unless you mean that the current state of the art quantum computers are not as good as classical computers. That said, I can think of two reasons why we might want ...


1

Quantum arithmetic circuits are useful in implementing "oracles" in various general quantum algorithms. For example, if we want to apply Grover's algorithm to solve a real Traveler's salesman problem, we need to implement the "oracle" inside the quantum circuit. Of course, in this case, we still need the conventional computer to prepare the quantum circuits ...


1

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


1

Grover's algorithm is a (quantum-)circuit-SAT solver. I suppose it could also be a literal black box solver, but it would only work with black boxes that don't decohere your entangled input state, and I'm having trouble believing that such things exist. I don't know why Grover or anyone else ever called it a database search algorithm. You can of course give ...


1

This may not exactly answer your question (which I suspect is still very much an open question, and what you're likely to get as answers are opinions), but have you looked at blind quantum computation? See here for another perspective. One way that we can describe that premise is to imagine some company claims to have developed a fabulous universal quantum ...


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