quantum computer of moderate complexity can do a calculation in 12 minutes that would require the best classical computer 1400 years to complete........the quantum computer calculates for 12 minutes and finally says the answer is.....4 my question would be: how can we ever possibly know for certain that the answer of "4" the quantum computer gave is actually the correct answer? its an answer but is it the correct answer? who can know and how can it be checked? it can't
Depends on the problem. However, broadly speaking, the observation that there are problems that are hard to solve but, given an answer and perhaps some adjoining "proof", easy to verify, is a foundational concept in complexity theory. For example, all decision problems in NP have solutions that can be verified in polynomial time, even if no polynomial-time algorithm is known that can solve the problem (i.e. the problem is not known to be in P). Plenty of elucidating examples can be found if you Google these terms. Note that verifying the answer to a specific problem is a straightforward and commonplace task, whereas demonstrating quantum supremacy is a novel and difficult challenge.
Dr. Vazirani, according to Aaronson's "Umeshisms" Contest, says clearly,
" If you have never been utterly wrong, you can never hope to be right. "
Today I attended Vazirani Sir lecture at IIT Delhi .
Prof also use these slides to explain the concepts .
quantum computer of moderate complexity can do a calculation in 12 minutes that would require the best classical computer 1400 years to complete........the quantum computer calculates for 12 minutes and finally says the answer is.....4
my question would be: how can we ever possibly know for certain that the answer of "4" the quantum computer gave is actually the correct answer? its an answer but is it the correct answer? who can know and how can it be checked? it can't
Depends on the problem. However, broadly speaking, the observation that there are problems that are hard to solve but, given an answer and perhaps some adjoining "proof", easy to verify, is a foundational concept in complexity theory. For example, all decision problems in NP have solutions that can be verified in polynomial time, even if no polynomial-time algorithm is known that can solve the problem (i.e. the problem is not known to be in P). Plenty of elucidating examples can be found if you Google these terms. Note that verifying the answer to a specific problem is a straightforward and commonplace task, whereas demonstrating quantum supremacy is a novel and difficult challenge.
As @jonrjeffrey said, many of these are "NP problems". hard to solve, very easy to verify