SyzygyRhythm
I was skimming the paper and came to this:
> This transformation is like an AND gate - it ignores the
index qubit and places the flag qubit in the state |1> if
and only if either of the original components had the
state |1> for the flag qubit.Shouldn't that be an OR gate?
Not only does the description above say "if and only if
either of the original components had the state |1>",
which is an OR, but the truth table listed above shows the
same thing for the flag qubit.Of course, one could say
it's an AND on the |0> states, which is just De Morgan's
law, but that's pretty awkward phrasing.
|
aix1
Anyone care to ELI5 the novelty or significance of this?
|
> tancop
if the PECTT (Physical Extended Church-Turing Thesis)
is true then the current standard way of connecting
classical gravity with quantum mechanics is wrong. the
authors take it as evidence for full quantum gravity
because the alternative is changing the Einstein
equations in some arbitrary complex way. im not a
physicist so this might be a bad explanation.the
extended thesis it depends on is "No physical
procedure can decide an NP-complete problem in
polynomially many steps." imo thats a very strong and
controversial assumption when we still dont know the
limits of what quantum computers can do.
|
> > red75prime
> we still dont know the limits of what quantum
computers can do.Well, we don't know the limits of
what classical computers can do too (P!=NP is not
proven).While not directly related to P!=NP,
historical claims of quantum superiority were
occasionally taken down by finding an efficient
classical algorithm.
|
> > bawolff
> the extended thesis it depends on is "No
physical procedure can decide an NP-complete
problem in polynomially many steps."I think part
of the confusion here, is that usually the
extended church turing thesis means that any
physical computation can be efficiently (in
polynomial time) simulated by a deterministic
turing machine. (And thus if quantum computers
exist and BQP is a superset of P, the proposition
is false). I've never seen it defined before as
above. But im definitely not a complexity
theorists.
|
> > > steve_gh
But remember that "efficient" in terms of P
and NP is about scaling. P == NP doesn't
necessarily mean that a practically efficient
algorithm can be found. The polynomial
exponents involved may be large: O(N^1000)
does eventually scale better than O(e^N), but
that doesn't mean it is practically useful!
|
> > misja111
But isn't PECTT already challenged by quantum
algorithms such as Shor and Grover?
|
> > > xdertz
Prime factorisation is not proven to be
NP-hard so the existence of a quantum
polynomial algorithm (Shor) has no bearing on
complexity classes other than showing that
prime factorisation is in BQP (quantum
polynomial). So it does challenge PECTT on
'vibes' as most experts think it is not in P,
but there is no mathematical proof for
it.Grover gives an at most quadratic speedup
for NP-hard problems, it does not turn a
non-polynomial algorithm into a polynomial
one.
|
> > > tromp
Shor doesn't solve an NP hard problem. It's
even possible that factoring and discrete log
are in P, while P != NP.The paper builds on
the results of
"Nonlinear quantum mechanics implies
polynomial-time solution for NP-complete and
#P problems"
by Abrams and Loyd [1], from which I quote:>
The last qubit now contains all the
information that we need; however, for small
s, a measurement of the last qubit will almost
always return |0>, yielding no information.
> We wish to distinguish between the cases s=0
and s>0.> Step 4. Repeatedly apply the
nonlinear operation to drive the states
representing these two cases apart at an
exponential rate: eventually, at a time
determined by a polynomial function of the
number of qubits n, the number of solutions s,
and the rate of spreading (Lyapunov exponent)
λ, the two cases will become macroscopically
distinguishable.[1]
https://arxiv.org/abs/quant-ph/9801041
|
> > > mofeing
No. As far as we know, no realization of a
quantum algorithm can solve NP-complete
problems in polynomial many steps.Some people
that worked on this topic told me that there
seems to be some improvements on the
quasi-optimal solution found, but that due to
the scale of current quantum computers, it
just have been tried out on small-sized
problems.Theoretically, there are some papers
suggesting that there are problems in BQP (the
computational model of quantum computers)
outside of NP [1] and even, the PH [2]
(Polynomial Hierarchy, the infinite hierarchy
of composition of NP and co-NP problems),
which is why we cannot still satisfactorily
say whether quantum computers can or cannot
solve NP-complete problems.The Wikipedia page
for BQP [3] does a good job showing what is
currently known.[1]
https://arxiv.org/abs/2209.10398
[2]
https://eccc.weizmann.ac.il/report/2018/107/
[3]
https://en.wikipedia.org/wiki/BQP#Relationship
_to_other_comp...
|
> > > > IsTom
As to the PH result, arguments on
relativized classes can be pretty
inconclusive. There's both oracles for P^A
= NP^A and P^B != NP^B.
|
> api
They use what looks like an impossible computational
result to back into the idea that this is indirect
evidence that gravity is quantized.The controversy
here is whether gravity is continuous (as classical
Einstein models it) all the way down, or if the large
scale behavior is built on a quantum foundation like
everything else.As far as I know most physicists
believe gravity must be quantized, but we have no
theory for it that works and plays nice with the well
validated relativistic stuff at scale.We have some
candidates like string theory and loop quantum gravity
but testing and refining them requires accelerators
the size of the solar system or direct access to a
black hole. The latter was the plot of Interstellar.
|
> casey2
They essentially are saying semiclassical gravity (a
broader theory subsuming classical) is theoretically
incorrect. Like doing the konami code IRL and getting
infinite money.
|
einpoklum
From the abstract:"Assuming [assumptions] we show that ...
can in principle solve..."Yeah, well, you know... that
doesn't sound as promising as the title.
|
> bawolff
Assuming X is true, that implies Y. We don't think Y
is true therefore we now doubt that X is true, is a
very standard thing to do in math.
|
> Garlef
That's the whole point of the article:"We show
[Assuming {competing physics theory} then {P =
NP}]"(or something along the lines)"But we actually
think P != NP... so [Assuming {P != NP} then
{competing physics theory} cant be true]"
|