undefined | Better HN

0 pointsbawolff25d ago0 comments

Well the author saysin that paragraph:

> In layman’s terms, I do not consider the “Exp-Minus-Log” function to be the continuous analog of the Boolean NAND gate or the universal quantum CCNOT/CSWAP gates.

But is there actually a combination of NANDs that find the roots of an arbitrary quintic? I always thought the answer was no but admittedly this is above my math level.

0 comments

reikonomusha25d ago

Combinations of the NAND gate can express any Boolean function. The Toffoli (CCNOT) or Fredkin (CSWAP) can express any reversible Boolean function, which is important in quantum computing where all gates must be unitary (and therefore reversible). The posited analog is that EML would be the "universal operator" for continuous functions.

zeroonetwothree25d ago

Yes, NAND gates can implement root finding algorithms for arbitrary polynomials. For example a variant of Newton’s method can be used (there are also better algorithms for circuits specifically).

This can be done in polynomial time as well.

This is fairly obvious if you think about that your computer can do the same thing and it’s just a fancy circuit.

floxy24d ago

Surely you can use EML to do root finding approximations also.

meindnoch25d ago

Solving polynomials over finite fields is trivial. Just try all combinations.

eru25d ago

You probably want a fast algorithm.

Compare https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.

bawolffOP25d ago

Sure, i guess i should have said something like with a polynomial circuit size or something.

However by the same token couldn't you use the same brute force approach with exp minus log?

What im really asking, are NAND gates really different here?

zeroonetwothree25d ago

How can you brute force real numbers?

bawolffOP24d ago

I meant for finite fields like the person i was responding to said.

j / k navigate · click thread line to collapse

0 comments

reikonomusha25d ago

zeroonetwothree25d ago

Yes, NAND gates can implement root finding algorithms for arbitrary polynomials. For example a variant of Newton’s method can be used (there are also better algorithms for circuits specifically).

This can be done in polynomial time as well.

This is fairly obvious if you think about that your computer can do the same thing and it’s just a fancy circuit.

floxy24d ago

Surely you can use EML to do root finding approximations also.

meindnoch25d ago

Solving polynomials over finite fields is trivial. Just try all combinations.

eru25d ago

You probably want a fast algorithm.

Compare https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.

bawolffOP25d ago

Sure, i guess i should have said something like with a polynomial circuit size or something.

However by the same token couldn't you use the same brute force approach with exp minus log?

What im really asking, are NAND gates really different here?

zeroonetwothree25d ago

How can you brute force real numbers?

bawolffOP24d ago

I meant for finite fields like the person i was responding to said.

j / k navigate · click thread line to collapse