Apakah ada analog kuantum dari masalah VP vs VNP?

8

Dari Wikipedia :

VP : Kelas VP adalah analog aljabar dari P; itu adalah kelas polinomialf derajat polinomial yang memiliki sirkuit ukuran polinomial atas lapangan tetapK .

VNP : Kelas VNP adalah analog dari NP. VNP dapat dianggap sebagai kelas polinomf untuk tingkat polinom sedemikian sehingga dengan monomial kita dapat menentukan koefisiennya dalamf efisien, dengan sirkuit ukuran polinomial.

Ada upaya untuk mengimplementasikan polinomial f menggunakan sirkuit kuantum, lih. arXiv: 1805.12445 . Jadi tidak ada ada saja analog kuantum dari VP vs VNP masalah? Apakah ada makalah tentang topik ini?

PS: Saya sudah mengajukan pertanyaan yang sangat terkait di situs Quantum Computing .

SD
sumber

Jawaban:

8

ffnnf=(fn)BQPQMAfG(x)xBQP#PVBQP#PVNPGfGfn(G)

#PVNP

VP2nBQP

BPPMABQPQMAVP

Ini bukan untuk mengatakan bahwa semua pendekatan ini tidak dapat bekerja, hanya untuk berbagi pemikiran tentang mereka. Saya harap seseorang dapat membuatnya bekerja!

Joshua Grochow
sumber