Konteks :
Ada beberapa makalah yang mempelajari implikasi dari kurva timelike tertutup (CTL) terhadap kompleksitas kuantum. Pada tahun 2008, Aaronson dan Watrous menerbitkan makalah terkenal mereka tentang topik ini yang menunjukkan bahwa bentuk perjalanan waktu tertentu dapat membuat komputasi klasik dan kuantum setara, yaitu komputer kuantum tidak memberikan keuntungan komputasi jika mereka dapat mengirim informasi ke masa lalu melalui kurva mirip waktu.
Pertanyaan :
Abstrak dengan jelas mengatakan bahwa kurva mirip waktu tertutup tidak diketahui keberadaannya. Jadi mengapa sebenarnya para ahli teori kompleksitas tertarik pada topik ini? Apakah studi CTC memberikan beberapa wawasan non-sepele tentang dasar-dasar teori kompleksitas?
Apakah ada garis dunia lain yang secara populer dipelajari dalam konteks teori kompleksitas? Jika ya, mengapa? Jika tidak, mengapa tidak (lalu apa yang istimewa dari CTC)?
Saya belum benar-benar sempat bekerja melalui makalah CTC, tapi saya mencoba untuk mendapatkan gambaran tentang "gambaran besar" di sini, untuk memahami motivasi di balik mempelajari topik ini.
Catatan : Saya sebelumnya bertanya tentang ini pada Quantum Computing SE, dalam konteks teori informasi kuantum, tetapi di sini saya secara khusus mencoba untuk melihatnya melalui lensa dari ahli teori kompleksitas atau ilmuwan komputer.
Jawaban:
Saya pikir pertanyaan besar di sini adalah "Seperti apa kompleksitas / kekuatan algoritma di alam semesta kita?" Jika kita mengabaikan relativitas dan QM, maka mesin vanilla Turing biasa adalah model yang layak. Tetapi relativitas dan QM adalah teori fisik terbaik kita saat ini untuk menjelaskan alam semesta, jadi pertanyaannya adalah apakah mengambil efek relativistik atau kuantum mengubah lanskap kompleksitas.
Dalam kasus QM, ini sekarang juga dimotivasi oleh potensi untuk rekayasa komputer kuantum yang berfungsi. Dalam kasus CTC, meskipun mereka tidak diketahui keberadaannya, pemahaman saya adalah mereka diizinkan menurut relativitas. Jadi pertanyaannya adalah: jika memang ada dan kita bisa memanfaatkannya, apa lagi yang bisa dilakukan komputer / bagaimana kompleksitas berubah? (Sama berlaku untuk QM, kami hanya lebih dekat dengan komputer kuantum yang ada.)
Akhirnya, sedikit tentang selera pribadi; Meskipun ini subyektif, pertanyaannya adalah setidaknya sedikit tentang rasa subjektif, jadi saya harap ini tepat. Saya sebenarnya ingin (secara damai) tidak setuju dengan usul sedikit di sini. Saya tidak berpikir bahwa semua sumber daya tentu menarik bagi sebagian besar ahli teori kompleksitas. Sebagai contoh, pada mesin Turing seseorang dapat mempertimbangkan pembalikan kepala sebagai sumber daya (berapa kali head tape berubah arah selama perhitungan?). Orang bahkan dapat menunjukkan ini adalah ukuran kompleksitas Blum, dengan teorema gap, percepatan, dan hierarki analog dengan waktu atau ruang. Saya telah melihat ini diberikan sebagai latihan yang menyenangkan di program sarjana, tetapi belum melihat banyak penelitian tentang hal itu. Mengapa? Mungkin Anda karena merasa lebih tergantung pada model dan kurang relevan dengan hal lain yang orang pedulikan tentang kompleksitas algoritma. Demikian pula, orang mempelajari komputasi hiper (apa yang bisa dilakukan TM dengan banyak langkah tak terhingga); walaupun tentu saja ada lebih banyak penelitian tentang ini, saya pikir itu kurang termotivasi dari realitas fisik ... Maksud saya di sini adalah untuk tidak memfitnah arah penelitian tertentu (pada kenyataannya, saya pikir mereka agak menarik), tetapi lebih dari itu saya tidak Menurut para ahli teori kompleksitas, mereka tertarik pada CTC "menurut definisi", tetapi ada pertimbangan tambahan yang membuat mereka menjadi menarik bagi banyak orang. (Dan, tentu saja, mungkin tidak semua ahli teori kompleksitas menganggapnya menarik!) walaupun tentu saja ada lebih banyak penelitian tentang ini, saya pikir itu kurang termotivasi dari realitas fisik ... Maksud saya di sini adalah untuk tidak memfitnah arah penelitian tertentu (pada kenyataannya, saya pikir mereka agak menarik), tetapi lebih dari itu saya tidak Menurut para ahli teori kompleksitas, mereka tertarik pada CTC "menurut definisi", tetapi ada pertimbangan tambahan yang membuat mereka menjadi menarik bagi banyak orang. (Dan, tentu saja, mungkin tidak semua ahli teori kompleksitas menganggapnya menarik!) walaupun tentu saja ada lebih banyak penelitian tentang ini, saya pikir itu kurang termotivasi dari realitas fisik ... Maksud saya di sini adalah untuk tidak memfitnah arah penelitian tertentu (pada kenyataannya, saya pikir mereka agak menarik), tetapi lebih dari itu saya tidak Menurut para ahli teori kompleksitas, mereka tertarik pada CTC "menurut definisi", tetapi ada pertimbangan tambahan yang membuat mereka menjadi menarik bagi banyak orang. (Dan, tentu saja, mungkin tidak semua ahli teori kompleksitas menganggapnya menarik!) tetapi ada pertimbangan tambahan yang membuat mereka menarik bagi banyak orang. (Dan, tentu saja, mungkin tidak semua ahli teori kompleksitas menganggapnya menarik!) tetapi ada pertimbangan tambahan yang membuat mereka menarik bagi banyak orang. (Dan, tentu saja, mungkin tidak semua ahli teori kompleksitas menganggapnya menarik!)
sumber
Maaf untuk jawaban "gambaran besar" dari seorang ahli teori non-kuantum, tetapi kontras ini mungkin membantu: Anda dapat menggambarkan algoritma sebagai studi tentang bagaimana menyelesaikan masalah komputasi, sedangkan teori kompleksitas mempelajari sumber daya (terutama waktu) yang diperlukan dalam teori untuk menyelesaikannya. Seberapa keras masalah ini benar-benar pada tingkat fundamental, dan bagaimana mereka dikelompokkan berdasarkan persyaratan sumber daya? Pertanyaan ini dianggap menarik terlepas dari berapa banyak atau jenis sumber daya apa yang dimiliki manusia.
Pertanyaan tentang berapa banyak waktu yang dibutuhkan dalam teori untuk menyelesaikan masalah berubah jika Anda mengizinkan CTC, oleh karena itu mereka menarik untuk teori kompleksitas dengan definisi.
Jadi saya merasa pertanyaan pertama Anda adalah seperti menanyakan mengapa para ahli teori komputasi akan mempelajari gelar Turing lebih tinggi dari nol; itu yang mereka lakukan.
sumber
Jika seseorang menganggap geodesik sebagai analisis geometris garis dunia dari pencarian Grover, tunjukkan di bawah metrik bahwa pencarian Grover mengikuti geodesik. Di bawah gangguan kecil juga, pencarian Grover bekerja dengan baik. Juga, mengingat suatu gangguan, di bawah jenis metrik kahler - metrik Studi-Fubini - Pencarian Grover tidak dapat mengikuti geodesi, lihat untuk studi gangguan . Referensi untuk optimalitas , dan studi geometris informasi dari pencarian Grover .
Alvarez et al mulai dengan menunjukkan pencarian Grover mengikuti geodesik di bawah metrik Fubini-Study, dan mereka mengeksplorasi algoritma kuantum lain seperti algoritma Shors. Meskipun ini dilakukan dalam konteks informasi Fisher, masih menunjukkan bahwa di bawah Fubini-Study, metrik Grover mengikuti geodesik. Juga, Alvarez et al menunjukkan di bawah asumsi informasi Fisher - "faktorisasi Shor tidak menjaga informasi Fisher yang konstan".
sumber