The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
Grover Adaptive Search for Constrained Polynomial Binary Optimization
Open accessAbstract
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Within the gate-model domain, a further distinction can be made between VQAs, Grover-based approaches [52, 118], and other gate-based approaches that have been mentioned above, e.g., References [15, 16, 24, 94].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [52]
The cited source says what the claim attributes to it.
In the citing paper
“An efficient way for the oracle construction within this algorithm that may allow it to be run on NISQ devices has been proposed [52].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [52]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2011) · Cited by 2,724
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Qiskit: An Open-source Framework for Quantum Computing
Aleksandrowicz, G., Alexander, T., Barkoutsos, P. K., Bello, L., Ben-Haim, Y., Bucher, D., Cabrera-Hernández, F. J., Carballo-Franquis, J., Chen, A., Chen, C.-F., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2562110 · Cited by 1,454
(1996) · Cited by 824
Towards quantum chemistry on a quantum computer
Lanyon, B. P., Whitfield, J. D., Gillett, G. G., Goggin, M. E., Almeida, M. P., Kassal, I., Biamonte, J. D., Mohseni, M., Powell, B. J., Barbieri, M., et al. (2010) · Nature Chemistry · doi:10.1038/nchem.483 · Cited by 796
Quantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 792
Validating quantum computers using randomized model circuits
Cross, A. W., Bishop, L. S., Sheldon, S., Nation, P. D., & Gambetta, J. M. (2019) · Physical Review A · doi:10.1103/physreva.100.032328 · Cited by 704
Quantum Amplitude Amplification and Estimation
Gilles Brassard, A., Høyer, P., Mosca, M., & Tapp, A. (2000) · doi:10.48550/arxiv.quant-ph/0005055 · Cited by 514
Robustness of adiabatic quantum computation
Childs, A. M., Farhi, E., & Preskill, J. P. (2001) · Physical Review A · doi:10.1103/physreva.65.012322 · Cited by 468
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 466
Self-citationVariational Quantum Linear Solver
Bravo-Prieto, C., LaRose, R., Cerezo, M., Subaşı, Y., Cincio, Ł., & Coles, P. J. (2023) · Quantum · doi:10.22331/q-2023-11-22-1188 · Cited by 459
Quantum Computation and Information
Lomonaco, S. J., & Brandt, H. E. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/305 · Cited by 408
Woerner, S., & Egger, D. J. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0130-6 · Cited by 364
Self-citationA Quantum Algorithm for Finding the Minimum
Durr, C., & Hoyer, P. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9607014 · Cited by 359
A new quantum ripple-carry addition circuit
Cuccaro, S. A., Draper, T. G., Kutin, S. A., & Moulton, D. P. (2004) · arXiv · doi:10.48550/arxiv.quant-ph/0410184 · Cited by 344
Option Pricing using Quantum Computers
Stamatopoulos, N., Egger, D. J., Sun, Y., Zoufal, C., Iten, R., Shen, N., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-07-06-291 · Cited by 337
Self-citationVariational Quantum Linear Solver
Bravo-Prieto, C., LaRose, R., Cerezo, M., Subasi, Y., Cincio, L., & Coles, P. J. (2019) · arXiv · doi:10.48550/arxiv.1909.05820 · Cited by 284
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269
Self-citationImproving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263
Self-citationQuantum computational finance: Monte Carlo pricing of financial derivatives
Rebentrost, P., Gupt, B., & Bromley, T. R. (2018) · Physical Review A · doi:10.1103/physreva.98.022321 · Cited by 262
Amplitude estimation without phase estimation
Suzuki, Y., Uno, S., Raymond, R., Tanaka, T., Onodera, T., & Yamamoto, N. (2020) · Quantum Information Processing · doi:10.1007/s11128-019-2565-2 · Cited by 249
Reverse quantum annealing approach to portfolio optimization problems
Venturelli, D., & Kondratyev, A. (2019) · Quantum Machine Intelligence · doi:10.1007/s42484-019-00001-w · Cited by 233
Addition on a Quantum ComputerPreprint
Draper, T. G. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0008033 · Cited by 196
Credit Risk Analysis Using Quantum Computers
Egger, D. J., Gutiérrez, R. G., Mestre, J. C., & Woerner, S. (2020) · IEEE Transactions on Computers · doi:10.1109/tc.2020.3038063 · Cited by 174
Self-citationQuantum Approximate Counting, Simplified
Aaronson, S., & Rall, P. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976014.5 · Cited by 155
A logarithmic-depth quantum carry-lookahead adder
Draper, T. G., Kutin, S., Rains, E. M., & Svore, K. M. (2006) · CaltechAUTHORS (California Institute of Technology) · doi:10.5555/2012086.2012090 · Cited by 146
Performance of hybrid quantum-classical variational heuristics for combinatorial optimization
Nannicini, G. (2019) · Physical Review E · doi:10.1103/physreve.99.013304 · Cited by 138
Quantum Computational Finance: Quantum Algorithm for Portfolio Optimization
Rebentrost, P., & Lloyd, S. (2024) · Künstliche Intell. · doi:10.1007/s13218-024-00870-9 · Cited by 128
Characterization of a Two-Transmon Processor with Individual Single-Shot Qubit Readout
Dewes, A., Ong, F. R., Schmitt, V., Lauro, R., Boulant, N., Bertet, P., Vion, D., & Esteve, D. (2012) · Physical Review Letters · doi:10.1103/physrevlett.108.057002 · Cited by 125
Grover's Quantum Algorithm Applied to Global Optimization
Baritompa, W. P., Bulger, D. W., & Wood, G. R. (2005) · SIAM Journal on Optimization · doi:10.1137/040605072 · Cited by 108
A logarithmic-depth quantum carry-lookahead adder
Draper, T. G., Kutin, S. A., Rains, E. M., & Svore, K. M. (2006) · Quantum Information and Computation · doi:10.26421/qic6.4-5-4 · Cited by 101
Approximate quantum Fourier transform with O(n log(n)) T gates
Nam, Y., Su, Y., & Maslov, D. A. (2020) · npj Quantum Information · doi:10.1038/s41534-020-0257-5 · Cited by 94
Implementing Pure Adaptive Search with Grover's Quantum Algorithm
Bulger, D. W., Baritompa, W. P., & Wood, G. R. (2003) · Journal of Optimization Theory and Applications · doi:10.1023/a:1023061218864 · Cited by 79
Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement
Braine, L., Egger, D. J., Glick, J., & Woerner, S. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3063635 · Cited by 51
Self-citationMoments of Gamma type and the Brownian supremum process area
Janson, S. (2010) · Probability Surveys · doi:10.1214/10-ps160 · Cited by 42
Quantum computational finance: quantum algorithm for portfolio optimizationPreprint
Rebentrost, P., & Lloyd, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03975 · Cited by 29
Foundational Patterns for Efficient Quantum ComputingPreprint
Gilliam, A., Venci, C., Muralidharan, S., Dorum, V., May, E. F., Narasimhan, R., & Gonciulea, C. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.11513 · Cited by 10
Self-citationMultiobjective Optimization Grover Adaptive Search
Barán, B., & Villagra, M. (2018) · Studies in computational intelligence · doi:10.1007/978-3-319-99648-6_11 · Cited by 1
Cited by
Sorted by citations
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 466
Self-citationHerman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 361
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“As in unconstrained discrete optimization, Grover search can be leveraged to achieve a quadratic speedup over brute-force search 77 .”
Self-citationFormulating and Solving Routing Problems on Quantum Computers
Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal Neira, D., & Greenberg, D. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3049230 · Cited by 145
Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
Gacon, J., Zoufal, C., Carleo, G., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-10-20-567 · Cited by 113
Self-citation
Metadata
- Authors
- Gilliam, A., Woerner, S., & Gonciulea, C.
- Affiliations
- JPMorgan Chase & Co (United States) (US)
- IBM Research - Zurich (CH)
- Venue
- Quantum
- Published
- 2021-04-08
- Volume
- 5
- Pages
- 428
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W2992763160
- Cited by
- 153
- References
- 44
- Citations by year
- 2026: 22 · 2025: 40 · 2024: 33 · 2023: 23 · 2022: 15 · 2021: 14
- FWCI
- 7.48
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Keywords
- QUBO, quantum oracle, quantum arithmetic, Toffoli gate, portfolio optimization, combinatorial optimization, quantum advantage, quantum computing hardware
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
