Question on claim that NP <= BQP from IACR eprint 2024/646

[Daniel Brown]

Dear PQC forum:

Recent IACR eprint 2024/646 claims NP \subseteq BQP.

If right, that would be quite bad for PQC, wouldn't it?

I haven't studied the eprint, nor am I an expert on BQP.  Naively, I'd be skeptical, though.

Are BQP experts here looking at this?

Best regards,

Dan

[D. J. Bernstein]

Daniel Brown writes:
> Recent IACR eprint 2024/646 claims NP \subseteq BQP.

2024/646 says it uses HHL. HHL is poly-time only when the condition
number of the input matrix is polynomially bounded. 2024/646 does not
report this critical limitation on HHL, and does not analyze the
magnitudes of any condition numbers.

---D. J. Bernstein

[Daniel Apon]

General advice for such situations:

1) https://scottaaronson.blog/?p=304
2) https://cohn.mit.edu/advice/
3) https://mathoverflow.net/questions/6912/on-the-proofs-and-disproofs-of-riemann-hypothesis#6916
4) https://math.stackexchange.com/questions/275194/how-does-a-non-mathematician-go-about-publishing-a-proof-in-a-way-that-ensures-i
5) https://math.stackexchange.com/questions/157250/spotting-crankery
6) https://terrytao.wordpress.com/career-advice/be-sceptical-of-your-own-work/

--Daniel

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20240429153707.1116471.qmail%40cr.yp.to.

[Jarek Duda]

In theory we could solve NP this way, but it would require exponential number of runs with postselection ...

However, having a process for state preparation |0>, in CPT symmetric physics in theory there also exist its symmetric counterpart <0|: just perform a process which in CPT perspective becomes the original state preparation process.

< psi_f | U | psi_i > <->^CPT <psi_i | U^dag | psi_f>

Having <0|, it would allow to enforce final values - act as postselectrion, but in single run - in theory such 2WQC could solve NP problems: https://arxiv.org/pdf/2308.13522

All the experimental evidence only confirm CPT symmetry of physics ( https://arxiv.org/pdf/0801.0287 ), what is required for Lorentz invariant local QFT ( https://en.wikipedia.org/wiki/CPT_symmetry ) - suggesting to at least test experimentally reversed state preparation processes, what seems doable e.g. for silicon quantum dots or photonic (below).

And maybe start thinking on nextgen PQC - resistant also to imperfect quantum NP solver, e.g. based on more difficult PSPACE problems ...

Best,
Jarek Duda

ps. Wolfram Quantum Framework supports 2WQC: https://community.wolfram.com/groups/-/m/t/3157512

-- dr Jarosław Duda Institute of Computer Science and Computer Mathematics, Jagiellonian University, Cracow, Poland http://th.if.uj.edu.pl/~dudaj/