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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
50 views

Clifford circuit approximation to a random Clifford circuit

Given a random Clifford state on $L$ qubits (defined as an infinite depth Clifford circuit acting on the zero state), what depth Clifford circuit is required to approximate this state to a given ...
user avatar
  • 330
5 votes
1 answer
64 views

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 ...
user avatar
  • 1,175
5 votes
1 answer
164 views

Multiplication by a Haar random unitary two times

Consider a Haar random unitary $U$. I am trying to compute the value (or put a bound on) \begin{equation} \mathbb{E}\left[\left|\langle 0^{n} |U^{2} |0^{n}\rangle\right|^{2}\right]. \end{equation} The ...
user avatar
1 vote
1 answer
41 views

Approximating the average of a rational function with respect to the Haar measure

Suppose I have a state $|\psi\rangle = U|0\rangle$ where $U$ is a $d$-dimensional unitary sampled uniformly with respect the Haar measure. I'm interested in computing or approximating analytically an ...
user avatar
  • 4,652
0 votes
2 answers
55 views

understanding QuantumCircuit.x() function

For Code 1 qc.x(0,1) throws error but not for code 2 . Please help me to understand code 1 ...
user avatar
2 votes
1 answer
44 views

What is the average amount of gates needed to implement a random Clifford gate?

Given a Clifford gate acting on $n$ qubits is implemented using its generators, what is the average number of gates needed to implement a random Clifford gate as a function of $n$?
user avatar
1 vote
0 answers
24 views

The phase of the eigenvalue for the LCU method and randomized product formula

If we implement the linear combination of unitary(LCU), $\tilde{U}=\sum_i p_i U_i$, onto its eigenstate, $|\psi \rangle$, we can express its eigenvalue as $re^{i\theta}$, where $\sum_ip_i=1$, $0\leq ...
user avatar
  • 11
0 votes
0 answers
18 views

How to define the phase obtained from the quantum phase estimation when using the randomized product formula as the Hamiltonian simulation?

Several randomized Hamiltonian simulation methods are developed in recent years. For example, the qDRIFT method is developed by Earl Campbell https://arxiv.org/pdf/1811.08017.pdf, or the randomized ...
user avatar
  • 11
0 votes
0 answers
29 views

Convergence of measure of products of random unitaries

I'm trying to read this paper by Emerson, Livine, Llyod (https://journals.aps.org/pra/abstract/10.1103/PhysRevA.72.060302), arXiv version: (https://arxiv.org/pdf/quant-ph/0503210.pdf). Essentially I ...
user avatar
  • 353
6 votes
1 answer
140 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 ...
user avatar
  • 2,107
2 votes
1 answer
127 views

At what depth and for what architecture are random quantum circuits $1$-designs?

I was confused about something related to quantum $1$ designs. Let us recap two facts we know about random circuit ensembles that form a $1$ design. $1$ design, for a quantum circuit over $n$ qubits, ...
user avatar
0 votes
1 answer
96 views

Random circuits with google cirq

For my dissertation I need to simulate random circuits and I have been trying to use google Cirq for that. Looking at the documentation I have seen how to create my own circuit and simulate it, but it ...
user avatar
  • 15
2 votes
1 answer
79 views

Random quantum circuits and general efficient POVM measurement

Let's consider a random quantum circuit $C$, applied to the $n$ qubit initial state $|0^{n}\rangle$, producing the state $|\psi\rangle$. Consider a general efficiently implementable $m$-outcome POVM ...
user avatar
2 votes
0 answers
87 views

Spreading of entanglement with depth for Haar random states

Consider a Haar random quantum state of depth $d$. Consider any bipartition of this state. According to this paper (page $2$): Haar-random states on $n$ qudits are nearly maximally entangled across ...
user avatar
4 votes
1 answer
160 views

Spoofing XQUATH with the Feynman method

Consider the XQUATH conjecture for random quantum circuits, as mentioned here. (XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There is no polynomial-time classical algorithm that ...
user avatar
3 votes
0 answers
50 views

Feynman method and polynomial time algorithm for XQUATH

Consider the Feynman algorithm for simulating quantum circuits, as given here. Consider the XQUATH conjecture for random quantum circuits from here, given by (XQUATH, or Linear Cross-Entropy Quantum ...
user avatar
2 votes
0 answers
28 views

What constitutes generic dynamics, and how is it different from a fully random function?

What constitutes generic dynamics? And how is it different from a fully random function? From what I understand, a fully random function is one that is "Haar" random. And generic dynamics, ...
user avatar
1 vote
1 answer
54 views

What is the counting argument for the number of elementary operations required for a random function?

What is the counting argument for the following statement (classical)? "A random function on n bits requires $e^{\Omega(n)}$ elementary operations." It appears in the introduction of PRL 116,...
user avatar
0 votes
1 answer
196 views

Quantum supremacy: shallow depth Haar random circuits and unitary designs

I had a confusion about shallow depth Haar random quantum circuits. In this paper, in Section B (related works), it is mentioned that Haar random quantum circuits form approximate $2$-designs only ...
user avatar
2 votes
1 answer
47 views

Quantum PRGN against Hard disk Forensics

We can make use of the Qbit to make a random string of bytes then as I have an office laptop and I can do some espionage by copying the files to my local disk from the network share and upload it to ...
user avatar
  • 127
1 vote
2 answers
128 views

Why is the Measurement Result Always 1? (expected to find uniformly random measurement)

I created a $|0\rangle$ state then applied $H$ gate to get $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ and then I meausred my state. But I always found 1. I expected to find 0 and 1 uniformly random ...
user avatar
  • 426
7 votes
1 answer
121 views

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 ...
user avatar
  • 1,661
0 votes
1 answer
203 views

What is the Clifford gates selection probability distribution used in the generation of randomized benchmarking circuits?

I've read that in standard randomized benchmarking implementations the random quantum circuits are generated through random gate selection from a uniformly distributed Clifford set of either 1 or 2-...
user avatar
  • 371
-1 votes
1 answer
152 views

Implementing a circuit that returns $|01\rangle$ and $|10\rangle$ with equal probability

Using Python how can I implement a quantum circuit that returns $|01\rangle$ or $|10\rangle$ using only $CX$, $RX$ and $RY$ gates, starting with random parametric gates as parameters and optimizing it ...
user avatar
2 votes
1 answer
277 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 ...
user avatar
  • 371
2 votes
1 answer
60 views

Randomness using simple parallel Hadamard circuit

I've recently tried to build a Random generator using 5 hadamard gates (shown as U2 below) measured to 5 classical bits in parallel as shown in the circuit image. I've executed this circuit for 8192 ...
user avatar
  • 23
1 vote
2 answers
134 views

If two reduced density matrices are equal, does that mean that the two subsystems are the same?

Suppose we have a $3$-qubit system at time $t_0$ in the state $$\vert{\psi(t_0)}\rangle= \vert{q_0}\rangle \otimes \vert{q_1} \rangle \otimes \vert{q_2}\rangle. $$ We want to check if, for instance, ...
user avatar
  • 103
0 votes
1 answer
77 views

How to create a Quantum circuit to implement the generation of 3-qubit uniform superposition wavefunction

I want to know experimentally or circuit wise diagram to know how to create a circuit that will produce 3-qubit uniform superposition wave function Can somebody help me in that Thank you in advance
user avatar
4 votes
1 answer
234 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 ...
user avatar
  • 49
3 votes
1 answer
116 views

What is the role of choosing the single-qubits randomly in Google quantum supremacy experiment?

In supremacy paper and part D of section VII of supplementary information (below), it is said that there is a pseudo-random number generator that is initialized with a seed called $s$; And then the ...
user avatar
  • 313
7 votes
1 answer
237 views

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. ...
user avatar
  • 313
2 votes
0 answers
25 views

How do we know that there exists a quantum circuit whose output distribution is #P-hard to calculate?

I am trying to understand the random quantum circuit sampling arguments for recent Google experiment, but struggling to understand why there exists a family of quantum circuit whose output ...
user avatar
2 votes
1 answer
366 views

How to make circuit for randomly selected gate?

I am trying to make a circuit for the randomly selected gates from a gate_list but I don't know how to put these selected gates in front of ...
user avatar
  • 391
2 votes
0 answers
56 views

How to randomly generate unoptimized stabilizer circuits?

I have to test a simulator with a high number of random stabilizer circuits. One way to create random stabilizer circuits is to generate random graph states and convert those to circuits, this, ...
user avatar
2 votes
0 answers
54 views

What is quantum gate's correponding circuit implementation? [closed]

We know that the symbol of a quantum gate like "x gate", "z gate" is an abstraction notation. For example, the Not-gate in classical computer is composed of 2 transistors. How can we know quantum gate'...
user avatar
  • 1,263
4 votes
2 answers
203 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 ...
user avatar
2 votes
1 answer
120 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 ...
user avatar
  • 7,017
7 votes
1 answer
251 views

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. ...
user avatar
  • 7,017
9 votes
1 answer
398 views

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 ...
user avatar
  • 7,017
6 votes
1 answer
664 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: ...
user avatar
8 votes
1 answer
865 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: ...
user avatar
12 votes
2 answers
792 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 ...
user avatar
4 votes
2 answers
338 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 ...
user avatar
  • 7,017
11 votes
1 answer
241 views

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 ...
user avatar
5 votes
1 answer
136 views

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, ...
user avatar
  • 7,017
5 votes
1 answer
557 views

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 ...
user avatar
  • 7,017
17 votes
1 answer
5k 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 ...
user avatar
  • 271