EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2208. Discrete optimization: Limitations of existing quantum algorithms
Invited abstract in session MC-42: Quantum Computing for Discrete and Combinatorial Optimization, stream Quantum Computing Optimization.
Monday, 12:30-14:00Room: 98 (building: 306)
Authors (first author is the speaker)
| 1. | Luis Perez
|
| Operations Management, IESEG | |
| 2. | Stefan Creemers
|
| UCLouvain |
Abstract
We investigate the limitations of existing quantum algorithms to solve discrete optimization problems. First, we discuss the quantum counting algorithm of Brassard et al. (1998), and show that it has performance that is equivalent to that of a brute-force approach when approximating the number of valid solutions. In addition, we show that a straightforward application of Grover's algorithm (referred to as GUM by Creemers and Pérez in an earlier paper) dominates any quantum counting algorithm when verifying whether a valid solution exists. Next, we discuss the nested quantum search algorithm of Cerf et al. (2000), and show that it is dominated by a classical nested search that uses an approach such as GUM to find (partial) solutions to (nested) problems. Last but not least, we also discuss amplitude amplification (a procedure that generalizes Grover's algorithm), and show (once more) that it may not be possible to outperform GUM.
Keywords
- Combinatorial Optimization
- Algorithms
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers