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


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

The Solovay-Kitaev algorithm is not practical. It is very useful theoretically because it proves that once you have a "dense" set of quantum gates (i.e. a set with which you can approximate any other quantum gate) you can approximate up to an arbitrary precision and quickly any quantum gate. In practice, the Solovay-Kitaev works as follow: Fill the space ...


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


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

Here are the corresponding decompositions of each gate with use of Toffoli and $X$ gates: The first one applies $X$ gate on the third qubit if control qubits are in the $|00\rangle$ state. The second one applies $X$ gate on the third qubit if control qubits are in the $|01\rangle$ state. The third one applies $X$ gate on the third qubit if control qubits ...


5

The issue is that you are using noisy hardware with imperfect operations and measurements. In particular, the most likely problem here is that after you prepare a qubit it immediately begins decaying towards the ground state $|0\rangle$ via interactions with the environment. Each qubit will be slightly more likely to be measured as 0 instead of 1 than you'd ...


4

A computational task doesn't have to have or be an application in order to be part of a valid model. If you claim that you can run a mile faster than I can, your four-minute mile doesn't have to be profitable employment in order to count. On the other hand, the random sampling demonstration with Sycamore certainly is an action of some kind performed by a ...


4

All quantum circuits can be simulated on a classical computer, but not all circuits take the same amount of time to simulate. If information about the circuit is known in advance, certain patterns may be exploited to significantly reduce time or memory consumption. The hardest type of circuit to simulate is one in which all qubits are entangled and there is ...


4

This is very similar to an function in terra random_circuit: https://github.com/Qiskit/qiskit-terra/blob/master/qiskit/circuit/random/utils.py#L30-L113 It randomly picks gates from the list of all the standard gates in terra. For example, you can run something like: from qiskit.circuit.random import random_circuit qr = random_circuit(10, 10, max_operands=3,...


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


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


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

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

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


3

In the framing of the question (which I believe to be asked in good faith), there seems to be at least two objections. Sampling from a set of strings is not clearly a function, and Sampling is a physical process, outside of computation. Initially, with regard to the first objection, I assert that sampling is a function, as a search problem. For example, ...


3

The Church-Turing thesis is not in and of itself a rigorous concept, but rather a judgment on rigorous concepts of computability. As such, it's negotiable. The language in Rosser's 1939 expository paper about provability and computability is biased towards deterministic algorithms. There is an important simplifying theorem here: If you only care about ...


3

Cirq does have some methods for generating random circuits, such as cirq.testing.random_circuit and cirq.random_rotations_between_grid_interaction_layers_circuit. That being said, in my experience, generic random circuit methods almost never do quite exactly what I need. I suspect that, for thesis-level work, you will need much more careful control over the ...


2

It's my understanding that in Google's quantum computational supremacy experiment, they have executed exactly the same random circuit up to 1M times, e.g up to 1M instances. They must perform that many experiments in order to have a chance of proving that they would have executed the experiment perfectly, at least (greater than or equal to) the fidelity to ...


2

In fact, you would need an astronomical circuit depth in order to get close to a uniformly random state, or even close to a randomly chosen probability distribution on the $2^{53}$ outputs. As a first estimate, consider how many different distributions you need in order to be within 1/8 of the total variation distance of any distribution on $N$ outputs. ...


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

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

It depends what you mean in wanting to say that the states "are the same". You probably mean all observable consequences on just that subsystem (i.e. measurements in arbitrary bases etc, without using the other qubits) are identical. In which case, it is sufficient that the reduced density matrices are the same - the whole point of the density ...


2

Density matrix completely describes the state of a system (or a subsystem). So if two density matrices are equal then the two states are equal (and vice versa). But you should not forget that The state of a subsystem can be mixed (e.g. look at the Bell state $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$). Density matrices uniquely describe mixed states as ...


2

A uniformly distributed superposition can be prepared by Hadamard gate. If you apply a Hadamard on single qubit in state $|0\rangle$ you get state $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Both states $|0\rangle$ and $|1\rangle$ are measured with same probability $50 \%$. To prepare uniformly distributed state having $n$ qubits, simply apply Hadamard on ...


2

I can't answer all your questions and I certainly am not an expert, but I have something to say about your first point. According to the first paper linked in my comment (by Aaronson and Chen), the hardness assumptions of BosonSampling hinges on the assumption that there is no $\text{BPP}^{\text{NP}}$ (this is BPP relative to an NP oracle) algorithm for ...


2

One potential combo is $ RY(\theta)$ on qubit 1, $CX$ from qubit 1 to qubit 2, then $RX(\pi)$ on qubit 2. This would be the following transformation: $$ |0\rangle |0\rangle \mapsto (\cos \frac{\theta}{2} |0\rangle + \sin \frac{\theta}{2}|1\rangle)|0\rangle \mapsto \cos \frac{\theta}{2} |00 \rangle + \sin \frac{\theta}{2} |11\rangle \mapsto \cos \frac{\theta}{...


2

To erase a HDD with a random numbers generated by quantum computer is in theory possible. Lets imagine you want to generate bit strings of length $n$, then you can simply put Hadamard gates on $n$ qubits. Such simple circuit prepares equal superposition of all $n$ bit long strings. When you put measurement after the Hadamard gates and run the circuit on a ...


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


1

We say that a function $f(n)$ is $O(n)$ if its bounded above by $n$ asymptotically, which is not to be confused with a function $f(n)$ being $\Omega(n)$ which means that $f(n)$ is bounded below by $n$ asymptotically. Also, there are $2^n$ boolean functions on $\{0,1\}^n$ since each boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is in one-to-one ...


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