تقرير
The PRODSAT phase of random quantum satisfiability
| العنوان: | The PRODSAT phase of random quantum satisfiability |
|---|---|
| المؤلفون: | Lee, Joon, Macris, Nicolas, Ravelomanana, Jean Bernoulli, Vantalon, Perrine |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics Quantum Physics |
| مصطلحات موضوعية: | Computer Science - Information Theory, Computer Science - Data Structures and Algorithms, Quantum Physics |
| الوصف: | The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of $N$ qubits consisting of a sum of $M$ random $k$-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2404.18447 |
| رقم الأكسشن: | edsarx.2404.18447 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |