Computational Complexity and Quantum Computing

I asked ChatGPT the following question. I will post ChatGPT's response along with it.

Question

Question:
In computer science, when measuring computational hardness, examples such as the Knapsack Problem and the Traveling Salesman Problem (TSP) are often used.
For exhaustive search of optimal solutions, the required time grows proportionally to 2^n for the knapsack problem and n! for TSP.
Thus, even when n is only in the two-digit range, computation explodes quickly. This means that even with faster computers, scaling up solvable problem size remains very difficult.

Recently, the feasibility of quantum computers has been widely discussed. Although still immature technologically, if such a machine were to mature and reach feasibility comparable to today’s supercomputers, would it avoid the explosion of complexity above, and make it easy to search for optimal solutions to the knapsack and TSP?

Or does this very problem-setting involve a hidden category mistake, making the question invalid or meaningless?

ChatGPT's Answer

The issues can be organized into the following two points.

1. Computational Explosion in Knapsack and Traveling Salesman Problems vs. Quantum Computing

·The Knapsack Problem and the Traveling Salesman Problem (TSP) are typical "NP-hard" problems.

·  With brute-force search, the Knapsack problem requires (2^n) time, and TSP requires (n!) time.

·  Quantum computers indeed provide significant speed-ups in some problems. For example:

o   Integer factorization → Shor’s algorithm achieves exponential improvement.

o   Search-type problems → Grover’s algorithm reduces exhaustive search from (N) to (\sqrt{N}).

However, for NP-hard problems, no known quantum algorithm reduces exponential time to polynomial time.
In other words, there is no evidence that quantum computing can "magically" solve NP-hard problems in general.

2. Technological Progress and the Possibility of a Category Mistake

·        Quantum computing mainly provides asymptotic improvements or efficiency gains in special cases.

o   With Grover’s algorithm, the Knapsack problem can be reduced from (2^n) to (2^{n/2}). This is an improvement, but still exponential.

o   For TSP, some restricted cases (e.g., satisfying the triangle inequality) can benefit from quantum speed-ups, but a polynomial-time solution remains out of reach.

·        Thus, believing that "once quantum computers are realized, NP-hard problems become easy" is close to a category mistake.

o   The hierarchy of computational complexity classes (P, NP, BQP, etc.) suggests theoretical barriers that hardware progress alone cannot overcome.

o   BQP (bounded-error quantum polynomial time) is not widely believed to contain NP as a whole.

3. Practical Outlook

·        Quantum computing may be more impactful in approximation algorithms or heuristic approaches, not in exact optimization.

·        Quantum annealing (e.g., D-Wave) is actively researched for near-optimal solutions of Knapsack or TSP at practical scales.

·        However, finding exact optimal solutions for large inputs will likely remain hard, even with advanced quantum technology.

✅ Summary

·        Even with quantum computers, exact solutions to Knapsack or TSP will not necessarily become "easy".

·        What can be expected is partial acceleration and approximate/heuristic improvements.

·        Assuming "quantum computing = universal solver of NP-hard problems" is a misconception (a category mistake).

·        The problem setting itself is meaningful, but one must not exaggerate the effect of quantum computing.

 

Diagram
·        P: Problems solvable in polynomial time

·        NP: Problems for which a solution can be verified in polynomial time

·        NP-complete: The class of the most difficult representative problems within NP

·        NP-hard: Problems at least as hard as NP, possibly outside NP

·        BQP: Problems solvable in polynomial time by quantum computation (including, for example, integer factorization, but not necessarily all of NP)

👉 As this diagram shows, the current understanding is that quantum computation (BQP) does not in general solve NP-hard problems in polynomial time.

Diagram（Hover your mouse pointer over the image below to display a clear separate screen.）