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.
Questions tagged [random-quantum-circuit]
83 questions
34
votes
1 answer
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 task
is to take a random (efficient) quantum…
grok
- 441
- 1
- 4
- 3
12
votes
2 answers
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 originally posted on the NASA NTRS but later…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
12
votes
1 answer
Sampling random circuits vs Solovay-Kitaev compiler
Suppose I want to obtain a gate sequence representing a particular 1 qubit unitary matrix.
The gate set is represented by a discrete universal set, e.g. Clifford+T gates or $\{T,H\}$ gates.
A well known approach to solve the problem is to use…
Yaroslav Kharkov
- 141
- 4
10
votes
2 answers
Number of qubits to achieve quantum supremacy?
Google's Sycamore paper describes achieving quantum supremacy on a $53$-qubit quantum computer. The layout of Sycamore is $n=6\times 9=54$ nearest neighbors, with one qubit nonfunctional. They apply $m=20$ total cycles in their experiment; each…
Mark Spinelli
- 15,378
- 3
- 26
- 83
9
votes
1 answer
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:
FIG 3. Control operations for the quantum supremacy…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
7
votes
1 answer
Are 20 repetitions of Sycamore's one- and 2-qubit gates sufficient to produce a uniformly random state?
In the answer to this question about random circuits, James Wootton states:
One way to see how well we [fully explore the Hilbert space] is to focus on just randomly producing $n$ qubit states. These should be picked uniformly from all possible…
Mark Spinelli
- 15,378
- 3
- 26
- 83
7
votes
0 answers
Complexity of a superposition of two random circuits
$\def\ket#1{|{#1}\rangle}$
Question
What is the minimum number of gates required to create the $N$-qubit state $\ket{\psi} = \frac{\ket{a} + \ket{b}}{\sqrt2}$ from the all-zeroes state, where one term in the superposition, $\ket{a}$, can be created…
Jordan Taylor
- 171
- 4
7
votes
1 answer
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 process each amplitude at least once in order to…
tparker
- 2,939
- 13
- 26
7
votes
1 answer
Could random quantum circuits be efficiently approximately simulated?
Google's landmark result last year was to compute a task with a quantum computer that a classical computer could not compute, and they chose random circuit sampling. Part of their justification was complexity-theoretic reasons that, if one can…
Sam Jaques
- 2,201
- 7
- 15
7
votes
1 answer
What did exactly Google do in simulating a random quantum circuit on a classical computer in supremacy experiment?
I've been working on Google quantum supremacy paper for quite some time now and I have a problem in understanding how exactly they simulate their actual random quantum circuit on a classical computer.
To be specific, in their quantum random circuit…
Ali s.k
- 313
- 1
- 5
6
votes
1 answer
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:
FIG 3. Control operations for the quantum supremacy…
Sanchayan Dutta
- 17,945
- 8
- 50
- 112
6
votes
1 answer
Can we amplify BPP algorithms with a random quantum circuit?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample $n$ bits, drawing a number $r$ uniformly from $[0,S]$; we…
Mark Spinelli
- 15,378
- 3
- 26
- 83
6
votes
1 answer
What is the HOG test and how would it help proving quantum supremacy?
Proposed experiments in achieving quantum supremacy, such as with BosonSampling or using random circuits, have been described as using a (not necessarily Turing complete) quantum computer to perform some sampling problem.
An example would be to…
Mark Spinelli
- 15,378
- 3
- 26
- 83
5
votes
0 answers
generator of a single-qubit random unitary operation
How should one choose the distribution of the real parameters $a,b$ in the Hamiltonian $H(a,b) = a \sigma_x + b \sigma_y$ so that the resulting unitary operation $e^{-iH(a,b)t}$ (for a fixed $t$) approximates a Haar-random distribution?
I’m familiar…
Mohan
- 329
- 1
- 4
5
votes
1 answer
What's the deal with quantum random number generators?
Classical computers are usually incapable of generating true random numbers as they are based on deterministic algorithms. To overcome this challenge, one can either use pseudo-random number generators or connect to some external stochastic system…
Mauricio
- 2,426
- 4
- 25