It does: “Random circuit sampling (RCS)”. This is a mathematical exercise.
…but that isn’t the important part. The important part is knowing if the answer it computed is right. How do you know if its right? This goes to your next question…
or what the complexity would be for a normal computer
The answer (not in this article but I’ve seen elsewhere) is essentially a million years of a regular computer.
So you see the challenge. We have an answer from the quantum computer, and a way to verify its actually right by using the slow method that we know would give is the right answer for sure, but its so far out of reach we can’t use the slow method in a feasible human lifetime.
So the breakthrough the article is calling out is what the researchers did instead. They built a way to have the quantum computer produce accurate answers (which quantum computers didn’t do reliably before because of the limits of science) on lots and lots of smaller shorter problems that we can compute on regular computers where we can verify the answers. Thats what the article is saying here:
“Encoding the circuit reduced the effective logical error rate to one tenth of the physical error rate, allowing the computation to maintain high fidelity despite the large number of operations.”
Here’s an analogy of how I understood what the researchers did:
Lets say you have 5 friends that love car road trips to places they’ve never been: Adam, Bill, Charlie, Dave, and Ethan. All of them refuse to use maps or a GPS. As you can imagine if any one of them gets in a car alone and just relies on their gut and signs they’ll likely not get to their destination. So instead the researchers put all 5 in one car.
Adam is in the driver’s seat and after the first hour has made every correct direction choice. Suddenly Adam is about to make a wrong turn Bill, Charlie, and Dave quickly tell Adam to make the right choice, while Ethan tells Adam to make a 3rd entire choice (which is also wrong). Adam goes by majority rule and chooses the suggested path from Bill, Charlie, and Dave. The car is still headed in the right direction. Ten minutes later Bill tells Adam to alter course, Adam, Charlie, Dave and Ethan contradict this, so the car still stays going the right direction. Another 20 minutes later Charlie and Dave tell Adam to take a turn. Adam, Bill and Ethan disagree and they car stays on the right path.
Eventually the car actually arrives at the destination a long way away from where they started. If any one of them were driving by themselves (or even with just one or two other drivers) the likelihood of a successful trip would drop to zero.
The researchers used a bunch of qubits (“drivers”) so even if there were bad directions given by some at any given moment, the overall result was successful. So the researchers can say even though we only had Adam, Bill, Charlie, Dave, and Ethan drive successfully from New York to Chicago, you can see how they work to stay on track and we they’d make it all the way to Los Angeles if asked. So just because we’ve never had Adam, Bill, Charlie, Dave, and Ethan drive from NYC to Los Angeles, you can trust that they could if we asked. So when we tell you we had them drive all the way from NYC to Anchorage Alaska, you can trust we’re telling you the truth and accept they got their successfully even if you didn’t do the slow walk all the way to Anchorage Alaska see them arrive with your own eyes.
The article states pretty explicitly that RCS is not what they did “a more structured alternative to RCS”
Hmm. If thats the form of the answer you’re looking for, I’m confused why you asked the question. My apologies, I thought you were trying to understand a new topic you didn’t have context for. I withdraw my long winded answer. Let me try again for you to your original two questions:
Article doesn’t say what they actually computed
“a more structured alternative to RCS”
or what the complexity would be for a normal computer
Your statement is factual. That information is not contained in the article.
Article doesn’t say what they actually computed or what the complexity would be for a normal computer
It does: “Random circuit sampling (RCS)”. This is a mathematical exercise.
…but that isn’t the important part. The important part is knowing if the answer it computed is right. How do you know if its right? This goes to your next question…
The answer (not in this article but I’ve seen elsewhere) is essentially a million years of a regular computer.
So you see the challenge. We have an answer from the quantum computer, and a way to verify its actually right by using the slow method that we know would give is the right answer for sure, but its so far out of reach we can’t use the slow method in a feasible human lifetime.
So the breakthrough the article is calling out is what the researchers did instead. They built a way to have the quantum computer produce accurate answers (which quantum computers didn’t do reliably before because of the limits of science) on lots and lots of smaller shorter problems that we can compute on regular computers where we can verify the answers. Thats what the article is saying here:
“Encoding the circuit reduced the effective logical error rate to one tenth of the physical error rate, allowing the computation to maintain high fidelity despite the large number of operations.”
Here’s an analogy of how I understood what the researchers did:
Lets say you have 5 friends that love car road trips to places they’ve never been: Adam, Bill, Charlie, Dave, and Ethan. All of them refuse to use maps or a GPS. As you can imagine if any one of them gets in a car alone and just relies on their gut and signs they’ll likely not get to their destination. So instead the researchers put all 5 in one car.
Adam is in the driver’s seat and after the first hour has made every correct direction choice. Suddenly Adam is about to make a wrong turn Bill, Charlie, and Dave quickly tell Adam to make the right choice, while Ethan tells Adam to make a 3rd entire choice (which is also wrong). Adam goes by majority rule and chooses the suggested path from Bill, Charlie, and Dave. The car is still headed in the right direction. Ten minutes later Bill tells Adam to alter course, Adam, Charlie, Dave and Ethan contradict this, so the car still stays going the right direction. Another 20 minutes later Charlie and Dave tell Adam to take a turn. Adam, Bill and Ethan disagree and they car stays on the right path.
Eventually the car actually arrives at the destination a long way away from where they started. If any one of them were driving by themselves (or even with just one or two other drivers) the likelihood of a successful trip would drop to zero.
The researchers used a bunch of qubits (“drivers”) so even if there were bad directions given by some at any given moment, the overall result was successful. So the researchers can say even though we only had Adam, Bill, Charlie, Dave, and Ethan drive successfully from New York to Chicago, you can see how they work to stay on track and we they’d make it all the way to Los Angeles if asked. So just because we’ve never had Adam, Bill, Charlie, Dave, and Ethan drive from NYC to Los Angeles, you can trust that they could if we asked. So when we tell you we had them drive all the way from NYC to Anchorage Alaska, you can trust we’re telling you the truth and accept they got their successfully even if you didn’t do the slow walk all the way to Anchorage Alaska see them arrive with your own eyes.
The article states pretty explicitly that RCS is not what they did “a more structured alternative to RCS”
Hmm. If thats the form of the answer you’re looking for, I’m confused why you asked the question. My apologies, I thought you were trying to understand a new topic you didn’t have context for. I withdraw my long winded answer. Let me try again for you to your original two questions:
“a more structured alternative to RCS”
Your statement is factual. That information is not contained in the article.