Gaussian boson sampling for binary optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916532741734400 |
|---|---|
| author | Cazalis, Jean Shah, Tirth Chai, Yahui Jansen, Karl Kühn, Stefan |
| author_facet | Cazalis, Jean Shah, Tirth Chai, Yahui Jansen, Karl Kühn, Stefan |
| contents | Binary optimization is a fundamental area in computational science, with wide-ranging applications from logistics to cryptography, where the tasks are often formulated as Quadratic or Polynomial Unconstrained Binary Optimization problems (QUBO/PUBO). In this work, we propose to use a parametrized Gaussian Boson Sampler (GBS) with threshold detectors to address such problems. We map general PUBO instance onto a quantum Hamiltonian and optimize the Conditional Value-at-Risk of its energy with respect to the GBS ansatz. In particular, we observe that, when the algorithm reduces to standard Variational Quantum Eigensolver, the cost function is analytical. Therefore, it can be computed efficiently, along with its gradient, for low-degree polynomials using only classical computing resources. Numerical experiments on 3-SAT and Graph Partitioning problems show significant performance gains over random guessing, providing a first proof of concept for our proposed approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14783 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Gaussian boson sampling for binary optimization Cazalis, Jean Shah, Tirth Chai, Yahui Jansen, Karl Kühn, Stefan Quantum Physics Binary optimization is a fundamental area in computational science, with wide-ranging applications from logistics to cryptography, where the tasks are often formulated as Quadratic or Polynomial Unconstrained Binary Optimization problems (QUBO/PUBO). In this work, we propose to use a parametrized Gaussian Boson Sampler (GBS) with threshold detectors to address such problems. We map general PUBO instance onto a quantum Hamiltonian and optimize the Conditional Value-at-Risk of its energy with respect to the GBS ansatz. In particular, we observe that, when the algorithm reduces to standard Variational Quantum Eigensolver, the cost function is analytical. Therefore, it can be computed efficiently, along with its gradient, for low-degree polynomials using only classical computing resources. Numerical experiments on 3-SAT and Graph Partitioning problems show significant performance gains over random guessing, providing a first proof of concept for our proposed approach. |
| title | Gaussian boson sampling for binary optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2412.14783 |