4 ms·

The cited paper[1] references "random circuit sampling" which is defined in [2] which then gets so heavy into abstract math, and I give up. Can someone explain

The cited paper[1] references "random circuit sampling" which is defined in [2] which then gets so heavy into abstract math, and I give up. Can someone explain this in terms an EE or programmer can understand? [1] https://arxiv.org/abs/2304.11119 https://arxiv.org/abs/2304.11119 [2] https://arxiv.org/abs/2007.07872 https://arxiv.org/abs/2007.07872

knorker 3y ago
Like reddit's ELI5 (explain it like I'm five), but ELIHAM (explain it like I (only) have a masters)? Yeah, if someone could please do that.
bob1029 3y ago
> The theoretical basis for these experiments depends on sampling the output distributions of random quantum circuits; unfortunately, understanding how this theoretical basis can be used to define quantum supremacy is an extremely difficult task. Anyone attempting to understand how this sampling task relates to quantum supremacy must study concepts from random matrix theory, mathematical analysis, quantum chaos, computational complexity, and probability theory. Resources connecting these concepts in the context of quantum supremacy are scattered and often difficult to find. At the end of the day, people writing these papers are also human. The very same sorts of humans who pad resumes with shiny technology and self-serving complexity. This might be a case of a rabbit you do not want to chase.
- Gravyness 3y ago
  > This might be a case of a rabbit you do not want to chase. I'm sure the researchers will all collectively realize this, if it were to be the case, and disregard their 12 year academic journey with their great salaries in favor of research into more important topics like world hunger, renewable energy, etc. I'm so sure that the percentage of sureness is an imaginary, quantum-entangled value between -7 and 13 billion percent.
  - junon 3y ago
    "academic journey" and "great salaries" generally don't go together.
  - cohomologo 3y ago
    I research QC. Feel free to explain how my skills could be used to meaningfully contribute to the problem of world hunger or renewable energy while also keeping me employed --- going back to college to train in a different field isn't feasible. If it's not so easy, then perhaps it's logical that QC researchers and AI researchers and software devs aren't all jumping ship to work on "more important topics"... You may just be spouting off, but I genuinely am asking. If someone else dissing QC research wants to make a pitch for a concrete plan on how to make a difference in the world with a physics PhD and years of experience in scientific computing, drop me a message.
B1FF_PSUVM 3y ago
> references "random circuit sampling" It's either Monte Carlo or bullshit.
- canadianfella 3y ago
  [dead]
swframe2 3y ago
(I don't have a background (or interest) in quantum computing) I've tried some of the "chat with pdf" websites for other topics. It seems like they could help you understand the paper. If you give it a try, could you report back here on how it worked for you.
pclmulqdq 3y ago
> Can someone explain this in terms an EE or programmer can understand? Unfortunately not. The physicists who are behind quantum computing don't think the same way, and go straight for the abstract math to solve any problem. I am pretty sure they don't understand that most of our progress on computing up to this point is because you don't need to go into Galois fields or discrete math to describe what a computer or algorithm does. I'm also pretty sure that they don't know of another way to think about it.
- OkayPhysicist 3y ago
  The second paper shared by the GP is actually just about as dumbed down as you can feasible get. The problem is that A) it uses some basic jargon, because it's fair to assume the only people interested in the result are people who understand the jargon and B) it's describing a completely impractical problem, designed to maximize the difference in performance between a quantum and classical computer rather than do anything particularly useful.
pyentropy 3y ago
Are you familiar with logic circuits (those made of gates like AND, OR, XOR, NAND)? Just like they are the founding blocks of classical computers, the founding block of quantum computers are quantum circuits. Quantum circuits are made of quantum logic gates like Hadamard, CNOT, Z, CZ, etc. Instead of bits as inputs and outputs, quantum logic gates have qubits. Unlike boolean logic where bits are 0 and 1, a qubit is a 2D vector [α β] where α and β are complex numbers, corresponding to a superposition of the zero and one bases: α * |0> + β * |1>. You can visualise a qubit as a point on a sphere, the so called Bloch sphere [1] There are multiple ways to implement a qubit, but you need to start with some quantum phenomenon. An example is the polarisation of a photon, so horizontal could be |0> and vertical polarisation could be |1> and the qubit is represented as complex vector of these two. If you've studied linear algebra you know manipulating a vector often involves linear transformations. Any linear transformation can be represented as a matrix - so applying gates is just doing matrix multiplication. Unary gates are 2x2 matrices and binary gates are 4x4 matrices - for photons they would be implemented with mirrors and optical waveplates. Measuring the polarisation at the end is the output. The output is not deterministic but it always follows the same distribution, so you could design a circuit that has |001> X% of the time, |010> Y%, |111> Z% of the time, etc. such that X + Y + Z + .. = 100%. I'm not too familiar with the details of random circuit sampling, but the idea is that you start with a big circuit that wasn't intentionally designed and therefore has no known properties we can exploit - instead it's a random mess of transformations to the qubits. A classical computer cannot run big quantum circuits - N gates with the 49 Google qubits requires like 2^49 * N^3 classical gates, so it won't be able to calculate the output distribution. However, what we can do is run the quantum circuit many times (do measurements on the quantum computer) and collect many samples. Given enough samples, a classical computer can verify whether there's consistency between them and whether an actual transformation produced them (and therefore quantum computation happened) or its just pure noise / garbage using cross entropy benchmarks [2]. Note that the purpose of the "random" in the random circuit is to introduce hardness and prevent cheating (assume that the classical computer is the "opponent" of the quantum computer); the circuits don't calculate anything useful / of human value. What's interesting is that once people with supercomputers saw the benchmark formula and analysed the constant factors, they found a loophole which let them run a classical algorithm which generates measurements/samples that satisfy the benchmark with 40K classical CPUs for a week, or even a single A100 within 140 days. Some of their success was due to the sheer power available and some is due to algorithmic cleverness (see: tensor networks). In my opinion, they are only disproving the Sycamore supremacy in a fussy way. [1] - https://en.wikipedia.org/wiki/Bloch_sphere https://en.wikipedia.org/wiki/Bloch_sphere [2] - https://en.wikipedia.org/wiki/Cross-entropy_benchmarking https://en.wikipedia.org/wiki/Cross-entropy_benchmarking
OkayPhysicist 3y ago
[2] is actually a phenomenally easy read for a physics paper, but it does assume an undergraduate physics degree's level of background. First, it's important to know that a quantum state (written as |letter>) is not directly observable. We can think of it as some vector, for which we can only apply an operation to to get out a scalar observable. A quantum circuit is a series of operations on a quantum state to create a different quantum state, which can be modeled as a matrix U, which is unitary (meaning U*U=1). The goal of "sampling a random quantum circuit" is trying to find the probability of observing some given observable if you keep applying random quantum circuits to a given input state.

knorker 3y ago

Like reddit's ELI5 (explain it like I'm five), but ELIHAM (explain it like I (only) have a masters)? Yeah, if someone could please do that.

bob1029 3y ago

> The theoretical basis for these experiments depends on sampling the output distributions of random quantum circuits; unfortunately, understanding how this theoretical basis can be used to define quantum supremacy is an extremely difficult task. Anyone attempting to understand how this sampling task relates to quantum supremacy must study concepts from random matrix theory, mathematical analysis, quantum chaos, computational complexity, and probability theory. Resources connecting these concepts in the context of quantum supremacy are scattered and often difficult to find. At the end of the day, people writing these papers are also human. The very same sorts of humans who pad resumes with shiny technology and self-serving complexity. This might be a case of a rabbit you do not want to chase.

Gravyness 3y ago
> This might be a case of a rabbit you do not want to chase. I'm sure the researchers will all collectively realize this, if it were to be the case, and disregard their 12 year academic journey with their great salaries in favor of research into more important topics like world hunger, renewable energy, etc. I'm so sure that the percentage of sureness is an imaginary, quantum-entangled value between -7 and 13 billion percent.
- junon 3y ago
  "academic journey" and "great salaries" generally don't go together.
- cohomologo 3y ago
  I research QC. Feel free to explain how my skills could be used to meaningfully contribute to the problem of world hunger or renewable energy while also keeping me employed --- going back to college to train in a different field isn't feasible. If it's not so easy, then perhaps it's logical that QC researchers and AI researchers and software devs aren't all jumping ship to work on "more important topics"... You may just be spouting off, but I genuinely am asking. If someone else dissing QC research wants to make a pitch for a concrete plan on how to make a difference in the world with a physics PhD and years of experience in scientific computing, drop me a message.

B1FF_PSUVM 3y ago

> references "random circuit sampling" It's either Monte Carlo or bullshit.

canadianfella 3y ago
[dead]

swframe2 3y ago

(I don't have a background (or interest) in quantum computing) I've tried some of the "chat with pdf" websites for other topics. It seems like they could help you understand the paper. If you give it a try, could you report back here on how it worked for you.

pclmulqdq 3y ago

> Can someone explain this in terms an EE or programmer can understand? Unfortunately not. The physicists who are behind quantum computing don't think the same way, and go straight for the abstract math to solve any problem. I am pretty sure they don't understand that most of our progress on computing up to this point is because you don't need to go into Galois fields or discrete math to describe what a computer or algorithm does. I'm also pretty sure that they don't know of another way to think about it.

OkayPhysicist 3y ago
The second paper shared by the GP is actually just about as dumbed down as you can feasible get. The problem is that A) it uses some basic jargon, because it's fair to assume the only people interested in the result are people who understand the jargon and B) it's describing a completely impractical problem, designed to maximize the difference in performance between a quantum and classical computer rather than do anything particularly useful.

pyentropy 3y ago

Are you familiar with logic circuits (those made of gates like AND, OR, XOR, NAND)? Just like they are the founding blocks of classical computers, the founding block of quantum computers are quantum circuits. Quantum circuits are made of quantum logic gates like Hadamard, CNOT, Z, CZ, etc. Instead of bits as inputs and outputs, quantum logic gates have qubits. Unlike boolean logic where bits are 0 and 1, a qubit is a 2D vector [α β] where α and β are complex numbers, corresponding to a superposition of the zero and one bases: α * |0> + β * |1>. You can visualise a qubit as a point on a sphere, the so called Bloch sphere [1] There are multiple ways to implement a qubit, but you need to start with some quantum phenomenon. An example is the polarisation of a photon, so horizontal could be |0> and vertical polarisation could be |1> and the qubit is represented as complex vector of these two. If you've studied linear algebra you know manipulating a vector often involves linear transformations. Any linear transformation can be represented as a matrix - so applying gates is just doing matrix multiplication. Unary gates are 2x2 matrices and binary gates are 4x4 matrices - for photons they would be implemented with mirrors and optical waveplates. Measuring the polarisation at the end is the output. The output is not deterministic but it always follows the same distribution, so you could design a circuit that has |001> X% of the time, |010> Y%, |111> Z% of the time, etc. such that X + Y + Z + .. = 100%. I'm not too familiar with the details of random circuit sampling, but the idea is that you start with a big circuit that wasn't intentionally designed and therefore has no known properties we can exploit - instead it's a random mess of transformations to the qubits. A classical computer cannot run big quantum circuits - N gates with the 49 Google qubits requires like 2^49 * N^3 classical gates, so it won't be able to calculate the output distribution. However, what we can do is run the quantum circuit many times (do measurements on the quantum computer) and collect many samples. Given enough samples, a classical computer can verify whether there's consistency between them and whether an actual transformation produced them (and therefore quantum computation happened) or its just pure noise / garbage using cross entropy benchmarks [2]. Note that the purpose of the "random" in the random circuit is to introduce hardness and prevent cheating (assume that the classical computer is the "opponent" of the quantum computer); the circuits don't calculate anything useful / of human value. What's interesting is that once people with supercomputers saw the benchmark formula and analysed the constant factors, they found a loophole which let them run a classical algorithm which generates measurements/samples that satisfy the benchmark with 40K classical CPUs for a week, or even a single A100 within 140 days. Some of their success was due to the sheer power available and some is due to algorithmic cleverness (see: tensor networks). In my opinion, they are only disproving the Sycamore supremacy in a fussy way. [1] - https://en.wikipedia.org/wiki/Bloch_sphere https://en.wikipedia.org/wiki/Bloch_sphere [2] - https://en.wikipedia.org/wiki/Cross-entropy_benchmarking https://en.wikipedia.org/wiki/Cross-entropy_benchmarking

OkayPhysicist 3y ago

[2] is actually a phenomenally easy read for a physics paper, but it does assume an undergraduate physics degree's level of background. First, it's important to know that a quantum state (written as |letter>) is not directly observable. We can think of it as some vector, for which we can only apply an operation to to get out a scalar observable. A quantum circuit is a series of operations on a quantum state to create a different quantum state, which can be modeled as a matrix U, which is unitary (meaning U*U=1). The goal of "sampling a random quantum circuit" is trying to find the probability of observing some given observable if you keep applying random quantum circuits to a given input state.