Questions tagged [random-quantum-circuit]
For questions about quantum circuits having a small (polynomial) number of quantum gates; each gate is defined randomly. Random quantum circuits may be implementable shortly, and be used in noisy, intermediate-scale quantum (NISQ) era. Sampling from a random quantum circuit is likely to be classically hard.
12
questions
12
votes
2
answers
1k
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 1): choice of gate set
I was recently going through the paper titled "Quantum supremacy using a programmable superconducting processor" by NASA Ames Research Centre and the Google Quantum AI team (note that the paper was ...
6
votes
1
answer
818
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 3): sampling
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
4
votes
1
answer
475
views
Help Identifying a Gate In Nielsen and Chuang
I am seeking help to identify the oracle gates listed in this example. I understand that the right-most one is a toffoli gate, but what are the other ones? Specifically, I do not understand what a ...
9
votes
1
answer
1k
views
Understanding Google's “Quantum supremacy using a programmable superconducting processor” (Part 2): simplifiable and intractable tilings
In Google's 54 qubit Sycamore processor, they created a 53 qubit quantum circuit using a random selection of gates from the set $\{\sqrt{X}, \sqrt{Y}, \sqrt{W}\}$ in the following pattern:
...
4
votes
2
answers
383
views
Do quantum supremacy experiments repeatedly apply the same random unitary?
It is my understanding that, given a quantum computer with $n$ qubits and a way to apply $m$ single- and 2-qubit gates, quantum supremacy experiments
Initialize the $n$ qubits into the all-zero's ket ...
4
votes
1
answer
300
views
Prove that uniformly random states have moments ${\bf E}_\psi|\langle x|\psi\rangle|^{2t}\sim1/\binom d t$
Im looking for the moments of Haar random states. Is it true that
$\textbf{E}_{\psi\sim \text{Haar}}|\langle x| \psi\rangle|^{2t}\sim \frac{1}{\binom{d}{t}}?$ How does one prove this?
20
votes
1
answer
7k
views
What exactly is "Random Circuit Sampling"?
Many people have suggested using "Random Circuit Sampling" to demonstrate quantum supremacy. But what is the precise definition of the "Random Circuit Sampling" problem? I've seen statements like "the ...
2
votes
1
answer
153
views
How does successfully sampling from a random quantum circuit invalidate the Extended Church-Turing Thesis?
According to these lecture notes from Berkeley, the Extended Church-Turing Thesis (ECT) asserts that:
...any "reasonable" model of computation can be efficiently simulated on a standard model such ...
6
votes
1
answer
316
views
What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?
My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to ...
4
votes
2
answers
248
views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
3
votes
2
answers
701
views
Computing expectation value of $|\langle z|C|0^n\rangle|^2$ over Haar random circuit
I am trying to understand the integration on page 4 of this paper. Consider a Haar random circuit $C$ and a fixed basis $z$. Each output probability of a Haar random circuit (given by $|\langle z | C |...
2
votes
1
answer
649
views
How to split a Quantum Circuit on a barrier in Qiskit?
Let's say I have a QuantumCircuit with multiple barriers as shown in the visual below:
How would I split up the ...