User talk:Jehochman

Boom!

Press button for large explosion.

The shors algorithm edit

can you explain what you meant by ballony? I don't see a problem with how it was before your edits Quantumly (talk) 00:22, 7 June 2023 (UTC)

The bit about Shor’s being efficient because of modular exponentiation was baloney. That operation is what makes shores so inefficient in terms of circuit complexity O(n^3). The binary Fourier transform is also not an efficiency. What makes Shor’s efficient is quantum parallelism and constructive/destructive interference. This allows a readout with significant probability of being a multiple of the order of the subgroup. Jehochman ^Talk 01:47, 7 June 2023 (UTC)

Yes, at first I thought the part about modular exponentiation made sense if you're looking at the slightly modified version using phase estimation, but yes it is ballony.

I also am not sure why you felt changing my edit of exponential back to sub-exponential? I really think the definition of sub-exponential including things like O(2^(n^k)) for 0 < k < 1 is a bit misleading. There are problems that are complete in EXP-time that take "sub-exponential" time if you use this definition (poly reductions still get you any exponential function) which sounds just wrong! Quantumly (talk) 01:54, 7 June 2023 (UTC)

I think we should fix the definition of sub-exponential because there’s a big difference between exponential and sub-exponential and we should be clear and accurate when talking about GNFS. Jehochman ^Talk 01:56, 7 June 2023 (UTC)

To be clear GNFS takes time less than all exponential algorithms, but more than all polynomial algorithms. It’s distinctly in between the two classes. Jehochman ^Talk 01:58, 7 June 2023 (UTC)

This is just not true.

EXP-complete problems are in a sense the hardest problems taking at least exponential time. I can give you examples of problems that are EXP-complete that have faster running times than GNFS. In fact, it may well be (though stupendous unlikely) that someone someday will be able to show that FACTORING is EXP-complete! (With the caveat that now also NP = EXP).

Think about it this way, it is possible to solve say, the Independent Set problem on planar graphs in roughly O(2^(n^(1/2))) which is sub-exponential, yet it is NP-complete and if there weren't any sub-exponential time complete problems in EXP, then the NP vs. EXP open problem would have been closed! Quantumly (talk) 02:04, 7 June 2023 (UTC)

A better defintion for sub-exponential will be just the intersection of DTIME(2^(n^epsilon)) for all epsilon greater than 0, this will eliminate the aforementioned confusion.

Also I should have wrote decision problems rather than just problems on my previous message, apologie! Quantumly (talk) 02:13, 7 June 2023 (UTC)

Go for it. Make sure to attach a good reference for anybody who wants to dive into the details. Jehochman ^Talk 03:28, 7 June 2023 (UTC)

I am sorry for being gruff. Quantum computing is widely misunderstood, and even writers who are experts can get confused. Jehochman ^Talk 01:55, 7 June 2023 (UTC)

Nomination for deletion of Template:Closeme

Template:Closeme has been nominated for deletion. You are invited to comment on the discussion at the entry on the Templates for discussion page. – Jonesey95 (talk) 13:29, 20 September 2023 (UTC)