Czy udowodniono, że obliczenia kwantowe nie są lepsze w rozwiązywaniu całkowitych problemów z NP niż obliczenia klasyczne, czy po prostu sądzi się?
Czy udowodniono, że obliczenia kwantowe nie są lepsze w rozwiązywaniu całkowitych problemów z NP niż obliczenia klasyczne, czy po prostu sądzi się?
Odpowiedzi:
Podejrzewa się, że problemów NP-zupełnych nie da się rozwiązać w kwantowym czasie wielomianowym (tzn. Że nie ma ich w BQP), ale nie zostało to udowodnione. Nie oczekujemy dowodów w najbliższej przyszłości, ponieważ oznaczałoby to, że P różni się od NP.