User talk:Jehochman: Difference between revisions

Content deleted Content added

Inline

Revision as of 23:16, 21 September 2023

Welcome to Jehochman's Talk Page
Please feel free to put your feet on the coffee table, and speak candidly. Or for more better relaxation, stretch yourself luxuriously on the chaise longue in Bishzilla's Victorian parlour and mumble incoherently.

Jehochman is busy with graduate school and may not respond swiftly to queries.

Boom!

Press button for large explosion.

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)[reply]

@@ Line 19: / Line 19: @@
 __TOC__
-== 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 [[User:Quantumly|Quantumly]] ([[User talk: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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 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! [[User:Quantumly|Quantumly]] ([[User talk: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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 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! [[User:Quantumly|Quantumly]] ([[User talk: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! [[User:Quantumly|Quantumly]] ([[User talk: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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 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. [[User:Jehochman|Jehochman]] <sup>[[User talk:Jehochman|Talk]]</sup> 01:55, 7 June 2023 (UTC)
 == Nomination for deletion of [[:Template:Closeme]] ==
 [[File:Ambox warning blue.svg|30px|link=]][[:Template:Closeme]] has been [[Wikipedia:Templates for discussion|nominated for deletion]]. You are invited to comment on the discussion at [[Wikipedia:Templates for discussion/Log/2023 September 20#Template:Closeme|'''the entry on the Templates for discussion page''']].<!--Template:Tfdnotice--> – [[User:Jonesey95|Jonesey95]] ([[User talk:Jonesey95|talk]]) 13:29, 20 September 2023 (UTC)