Apakah komputasi kuantum memberikan peningkatan dalam evaluasi fungsi transendental?

Dengan masalah factorisation integer, algoritma Shor dikenal untuk memberikan peningkatan (eksponensial?) Yang substansial dibandingkan dengan algoritma klasik. Apakah ada hasil yang serupa mengenai matematika yang lebih mendasar, seperti mengevaluasi fungsi transendental?

Katakanlah saya ingin menghitung , atau . Di dunia klasik, saya mungkin menggunakan ekspansi seperti seri Taylor atau beberapa algoritma iteratif. Apakah ada algoritma kuantum yang bisa lebih cepat dari apa yang bisa dilakukan komputer klasik, baik asimptotnya lebih baik, lebih sedikit iterasi dengan presisi yang sama, atau lebih cepat pada waktu jam dinding? $\sin2$ $\ln{5}$ $\cosh10$

algorithm speedup Norrius
sumber

Sudah ada algoritma klasik yang dapat mengevaluasi mereka ke presisi yang wajar (misalnya 80 bit) dalam beberapa siklus clock (dan mereka sebenarnya diimplementasikan pada CPU); tampaknya tidak mungkin bahwa QC dapat bekerja secara signifikan lebih cepat dari itu. Apakah Anda bertanya tentang presisi yang sangat tinggi (misalnya 1 juta bit)?

ponco

@poncho Memang masuk akal bahwa hal-hal dasar seperti ini telah dioptimalkan untuk mendekati kesempurnaan, tapi saya bertanya-tanya apakah ada sesuatu dalam fungsi ini yang dapat dieksploitasi menjadi lebih cepat pada QC. Bahkan jika efeknya hanya dapat dilihat pada persyaratan presisi ekstrim.

Norrius

@poncho "sepertinya tidak mungkin QC dapat bekerja lebih cepat dari itu" Orang-orang berpikir bahwa tidak mungkin akan ada perbaikan pada algoritma multiplikasi naif, tetapi sekarang kita memiliki Karatsuba. Anda mungkin bertanya-tanya apakah kami ingin algoritma yang lebih baik (ya, misalnya untuk presisi, seperti yang Anda sebutkan), tetapi sebenarnya tidak begitu aneh untuk mengharapkan peningkatan.

Kadal diskrit

Apakah komputasi kuantum memberikan peningkatan dalam evaluasi fungsi transendental?

Jawaban: