5 ms·

The work is about simulating wide-but-shallow quantum circuits (e.g. 49 qubits with 27 layers of operations, or 56 qubits x 23 layers [edit: HN title much bette

The work is about simulating wide-but-shallow quantum circuits (e.g. 49 qubits with 27 layers of operations, or 56 qubits x 23 layers [edit: HN title much better now]). The article entirely fails to mention the depth restriction. (The paper is very upfront about it: [1].) Personally, I happen to agree with Scott Aaronson's take [2]: > The goal, with sampling-based quantum supremacy, was always to target the “sweet spot,” which we estimated at around 50 qubits, where classical simulation is still possible, but it’s clearly orders of magnitude more expensive than doing the experiment itself. If you like, the goal is to get as far as you can up the mountain of exponentiality, conditioned on people still being able to see you from the base. Why? Because you can. Because it’s there. Because it challenges those who think quantum computing will never scale: explain this, punks! But there’s no point unless you can verify the result. Although doing that and pushing into a regime that no one can simulate until a couple years later sure wouldn't hurt. 1: https://arxiv.org/abs/1710.05867 https://arxiv.org/abs/1710.05867 2: https://www.scottaaronson.com/blog/?p=3512 https://www.scottaaronson.com/blog/?p=3512

taneq 9y ago
> But there’s no point unless you can verify the result. I thought there were quite a few problems (like factoring) which were hard to generate a correct answer, but easy to check whether an answer is correct?
- deleted 9y ago
  [deleted]
- jdironman 9y ago
  A bit off topic to your question, but this reminds me. Where are we exactly progress wise with P vs. NP problem? I've not thought to track the millennium problems in a while. I'm sure I would have heard if something substantial had arisen though. I used to work with it at some point on specific variation of the problem with was the dorm room housing problem [1]. That particular scenario always stood out to me as something that should be relatively easy to solve and I worked on it for a few years. Anyways, I'm way off topic now. [1] http://www.claymath.org/millennium-problems/p-vs-np-problem http://www.claymath.org/millennium-problems/p-vs-np-problem
  - Aardwolf 9y ago
    Every now and then there is a paper that attempts proving P=NP or attempts proving P!=NP, I've seen different papers on hacker news several times. The most interesting link someone posted was this one listing many such papers, nicely indicating [equal], [not equal], [undecidable] or [unprovable]: http://web.archive.org/web/20171006224902/https://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://web.archive.org/web/20171006224902/https://www.win.tu... Archive link because original page has certificate error :(
    - jdironman 9y ago
      I am especially intrigued by the argument made by Nicholas Argall. In that the question of whether P = NP or not is incomplete in and of itself.[1] I think this is very true on the basis that not all of these problems are the same or present the same criteria to solve. I think understanding these problems is going to require thinking from a different depth though. It's fun to me to think about and try to wrap my head around. I'm no expert but have a lot of fun with it. http://web.archive.org/web/20170817220728/http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt http://web.archive.org/web/20170817220728/http://www.win.tue...
      - thethirdone 9y ago
        The argument put forward in the link misrepresents Godel's theorem. > 6) Therefore, no consistent and complete definition of the set NP is possible Rationale: If we accept that the set NP can only be rigorously defined via a language, this conclusion follows from the premises above. This doesn't even make sense. Definitions do not change a languages completeness or consistency; they simply relate a new concept to previously defined concepts. > 7) Therefore, no consistent and complete statement of the problem of P=NP is possible Comment: A conclusion which is not only proven in this paper, but supported by the years of argument between mathematicians regarding the relevance of proposed answers to the problem. This is not supported from Godel's theorem. The fact that you need a non-complete system to be able to reason about something does not mean the theorem you want to prove is not provable. The main problem with the argument is that it works for other theorems that have been formally proven.
- deleted 9y ago
  [deleted]
- greeneggs 9y ago
  In theoretical computer science, NP is the class of problems where it is easy to check an answer but (presumably) difficult to generate an answer. There are many, many problems in NP. However, quantum computers are not expected to be able to efficiently solve NP problems. Factoring is thought to be an easier sort of NP problem, known sometimes as NP-intermediate [1]. (This means it is in NP, but not "NP-complete.") So quantum computers have a chance at factoring efficiently, and in fact they do. There are other NP-intermediate problems like discrete logarithm that quantum computers can also solve, but NP-intermediate problems are not as common (in real life) as NP-complete problems and quantum computers still can't solve a lot of them as far as we know. [1] https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
- Strilanc 9y ago
  There are, but quantum computers won't have the ability to solve these problems for many years to come (because error correction is required). Quantum supremacy will happen sooner because it can choose from more esoteric problems that are easier to sample.

taneq 9y ago

> But there’s no point unless you can verify the result. I thought there were quite a few problems (like factoring) which were hard to generate a correct answer, but easy to check whether an answer is correct?

deleted 9y ago
[deleted]
jdironman 9y ago
A bit off topic to your question, but this reminds me. Where are we exactly progress wise with P vs. NP problem? I've not thought to track the millennium problems in a while. I'm sure I would have heard if something substantial had arisen though. I used to work with it at some point on specific variation of the problem with was the dorm room housing problem [1]. That particular scenario always stood out to me as something that should be relatively easy to solve and I worked on it for a few years. Anyways, I'm way off topic now. [1] http://www.claymath.org/millennium-problems/p-vs-np-problem http://www.claymath.org/millennium-problems/p-vs-np-problem
- Aardwolf 9y ago
  Every now and then there is a paper that attempts proving P=NP or attempts proving P!=NP, I've seen different papers on hacker news several times. The most interesting link someone posted was this one listing many such papers, nicely indicating [equal], [not equal], [undecidable] or [unprovable]: http://web.archive.org/web/20171006224902/https://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://web.archive.org/web/20171006224902/https://www.win.tu... Archive link because original page has certificate error :(
  - jdironman 9y ago
    I am especially intrigued by the argument made by Nicholas Argall. In that the question of whether P = NP or not is incomplete in and of itself.[1] I think this is very true on the basis that not all of these problems are the same or present the same criteria to solve. I think understanding these problems is going to require thinking from a different depth though. It's fun to me to think about and try to wrap my head around. I'm no expert but have a lot of fun with it. http://web.archive.org/web/20170817220728/http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt http://web.archive.org/web/20170817220728/http://www.win.tue...
    - thethirdone 9y ago
      The argument put forward in the link misrepresents Godel's theorem. > 6) Therefore, no consistent and complete definition of the set NP is possible Rationale: If we accept that the set NP can only be rigorously defined via a language, this conclusion follows from the premises above. This doesn't even make sense. Definitions do not change a languages completeness or consistency; they simply relate a new concept to previously defined concepts. > 7) Therefore, no consistent and complete statement of the problem of P=NP is possible Comment: A conclusion which is not only proven in this paper, but supported by the years of argument between mathematicians regarding the relevance of proposed answers to the problem. This is not supported from Godel's theorem. The fact that you need a non-complete system to be able to reason about something does not mean the theorem you want to prove is not provable. The main problem with the argument is that it works for other theorems that have been formally proven.
deleted 9y ago
[deleted]
greeneggs 9y ago
In theoretical computer science, NP is the class of problems where it is easy to check an answer but (presumably) difficult to generate an answer. There are many, many problems in NP. However, quantum computers are not expected to be able to efficiently solve NP problems. Factoring is thought to be an easier sort of NP problem, known sometimes as NP-intermediate [1]. (This means it is in NP, but not "NP-complete.") So quantum computers have a chance at factoring efficiently, and in fact they do. There are other NP-intermediate problems like discrete logarithm that quantum computers can also solve, but NP-intermediate problems are not as common (in real life) as NP-complete problems and quantum computers still can't solve a lot of them as far as we know. [1] https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
Strilanc 9y ago
There are, but quantum computers won't have the ability to solve these problems for many years to come (because error correction is required). Quantum supremacy will happen sooner because it can choose from more esoteric problems that are easier to sample.