17
votes
What exactly is "Random Circuit Sampling"?
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 ...
- 11.2k
9
votes
Sampling random circuits vs Solovay-Kitaev compiler
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 ...
- 4,787
8
votes
Accepted
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling
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 ...
glS♦
- 23.4k
8
votes
Accepted
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings
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 ...
- 10.7k
8
votes
Accepted
Multiplication by a Haar random unitary two times
There is an explicit formula for the integral with respect to the Haar measure of any polynomial in the entries of a unitary and its conjugate, due to Collins and Śniady:
Benoît Collins and Piotr ...
- 5,158
6
votes
Help Identifying a Gate In Nielsen and Chuang
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 ...
- 4,261
6
votes
Accepted
What is the HOG test and how would it help proving quantum supremacy?
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 ...
- 33.3k
5
votes
Accepted
Computing expectation value of $|\langle z|C|0^n\rangle|^2$ over Haar random circuit
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 ...
- 20.8k
5
votes
Accepted
Compute the large $n$ distribution of $|\langle z_i|\psi\rangle|^2$ over Haar random quantum states
In the following, I'll show the evaluation of the probability densities of the transition probabilities: $|\langle \psi | z\rangle^2$ and their pairwise independence. I didn't work out the full mutual ...
- 2,495
5
votes
Accepted
Randomness using simple parallel Hadamard circuit
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 ...
- 33.3k
5
votes
Accepted
Random circuits with google cirq
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, ...
- 33.3k
4
votes
Accepted
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
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 ...
- 10.7k
4
votes
Accepted
How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?
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 ...
- 1,251
4
votes
Accepted
What did exactly Google do in simulating a random quantum circuit on a classical computer in supremacy experiment?
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 ...
- 96
4
votes
Accepted
How to make circuit for randomly selected gate?
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 ...
- 1,572
4
votes
Accepted
At what depth and for what architecture are random quantum circuits $1$-designs?
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_{...
- 4,497
3
votes
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
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 ...
- 10.7k
3
votes
Accepted
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
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 ...
- 1,251
3
votes
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
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 ...
- 899
3
votes
Accepted
Do quantum supremacy experiments repeatedly apply the same random unitary?
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 ...
glS♦
- 23.4k
3
votes
Accepted
Quantum supremacy: shallow depth Haar random circuits and unitary designs
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 ...
- 4,497
3
votes
Spoofing XQUATH with the Feynman method
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 ...
- 326
3
votes
Prove that uniformly random states have moments ${\bf E}_\psi|\langle x|\psi\rangle|^{2t}\sim1/\binom d t$
The factor in your claim is wrong. It should be $\binom{d+t-1}{t}^{-1}$. The correct claim follows from the identity
$$
\int |\psi\rangle\langle\psi|^{\otimes t} d\psi = \binom{d+t-1}{t}^{-1} P_{\...
- 4,497
3
votes
How do I prove these gate identities?
For (a), and in accordance with the hint:
With controls = 00, the target qubit is not operated on (because all the gates have their controls set to 0 and so they do not affect the target).
With ...
- 334
2
votes
Do quantum supremacy experiments repeatedly apply the same random unitary?
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 ...
- 10.7k
2
votes
What is the role of choosing the single-qubits randomly in Google quantum supremacy experiment?
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 ...
- 10.7k
2
votes
Accepted
Are 20 repetitions of Sycamore's one- and 2-qubit gates sufficient to produce a uniformly random state?
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 ...
- 1,251
2
votes
If two reduced density matrices are equal, does that mean that the two subsystems are the same?
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, ...
- 55.7k
2
votes
Accepted
If two reduced density matrices are equal, does that mean that the two subsystems are the same?
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 ...
- 6,711
2
votes
How to create a Quantum circuit to implement the generation of 3-qubit uniform superposition wavefunction
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 ...
- 13.6k
Only top scored, non community-wiki answers of a minimum length are eligible