Dalam kompleksitas komputasi optik linier ( ECCC TR10-170 ), Scott Aaronson dan Alex Arkhipov berpendapat bahwa jika komputer kuantum dapat disimulasikan secara efisien oleh komputer klasik maka hierarki polinomial runtuh ke tingkat ketiga. Masalah yang memotivasi adalah pengambilan sampel dari distribusi yang ditentukan oleh jaringan linear-optik; distribusi ini dapat dinyatakan sebagai permanen dari matriks tertentu. Dalam kasus klasik semua entri dari matriks adalah non-negatif, dan ada algoritma waktu polinomial probabilistik, seperti yang ditunjukkan oleh Mark Jerrum, Alistair Sinclair, dan Eric Vigoda (JACM 2004, doi: 10.1145 / 1008731.1008738). Dalam kasus kuantum entri adalah bilangan kompleks. Perhatikan bahwa dalam kasus umum (ketika entri tidak harus non-negatif) permanen tidak dapat didekati bahkan dalam faktor konstan, oleh hasil 1979 klasik Valiant.
Makalah ini mendefinisikan distribusi didefinisikan oleh matriks , dan masalah pengambilan sampel
Input BosonSampling : matrix Contoh: dari distribusi
Menggunakan hasil kekerasan tampaknya menjadi bukti yang lemah untuk pemisahan antara dunia klasik dan kuantum, karena ada kemungkinan bahwa kelas matriks dalam pengaturan kuantum tertentu semua akan memiliki bentuk khusus. Mereka mungkin memiliki entri yang kompleks, tetapi mungkin masih memiliki banyak struktur. Oleh karena itu bisa ada prosedur pengambilan sampel yang efisien untuk matriks seperti itu, meskipun masalah umumnya adalah # P-hard.
Bagaimana cara penggunaan BosonSampling di koran menghindari kelas yang mudah?
Makalah ini menggunakan banyak latar belakang yang tidak saya miliki dalam kompleksitas kuantum. Mengingat semua orang kuantum di situs ini, saya akan sangat menghargai pointer ke arah yang benar. Bagaimana argumen akan bertahan jika seseorang menemukan bahwa kelas matriks bernilai kompleks yang terlihat dalam pengaturan eksperimental tertentu benar-benar sesuai dengan kelas distribusi yang mudah diambil sampelnya? Atau adakah sesuatu yang melekat dalam sistem kuantum yang menjamin ini tidak dapat terjadi?
sumber