11 papers
Cycle Codes and Decoded Quantum Interferometry
Anuj Apte, Shouvanik Chakrabarti, Andi Gu +6
Decoded Quantum Interferometry (DQI) reduces optimization problems with two-variable constraints to decoding cycle codes. For one such problem, namely MaxCut, prior work showed tha…
Provable Classical and Quantum Local Algorithms for Max--Cut and Quantum Advantage at Moderate Girth
Anuj Apte, Abid Khan, Edward Farhi +3
Broadening the study of quantum optimization algorithms from binary to -element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage…
Scale Weight Decay and Train Better
Anuj Apte
The discovery of scaling laws has motivated training neural networks on ever increasing quantities of data. This is typically done with a constant decoupled weight decay which caus…
Anytime Training with Schedule-Free Spectral Optimization
Anuj Apte, Pranav Deshpande, Niraj Kumar +2
Standard neural network training relies on learning-rate schedules tied to a fixed horizon, leading to strong path dependence and costly re-tuning as data availability changes. Sch…
Regularized Warm-Started Quantum Approximate Optimization and Conditions for Surpassing Classical Solvers on the Max-Cut Problem
Zichang He, Anuj Apte, Brandon Augustino +4
Demonstrating quantum heuristics that outperform strong classical solvers on large-scale optimization remains an open challenge. Here we introduce Regularized Warm-Started QAOA (RW…
Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut
Anuj Apte, Sami Boulebnane, Yuwei Jin +3
Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remain…
A 0.8395-approximation algorithm for the EPR problem
Anuj Apte, Eunou Lee, Kunal Marwaha +3
We give an efficient 0.8395-approximation algorithm for the EPR Hamiltonian. Our improvement comes from a new nonlinear monogamy-of-entanglement bound on star graphs and a refined…
Mechanisms for Quantum Advantage in Global Optimization of Nonconvex Functions
Dylan Herman, Guneykan Ozgul, Anuj Apte +4
We present new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, expanding the scope of quantum advantage beyond traditional tunneling-b…
Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
Anuj Apte, Ojas Parekh, James Sud
We explain how the maximum energy of the Quantum MaxCut, XY, and EPR Hamiltonians on a graph are related to the spectral radii of the token graphs of . From numerical study,…
Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings
Anuj Apte, Eunou Lee, Kunal Marwaha +2
We introduce a -approximation algorithm for Quantum MaxCut and a -approximation algorithm for the EPR Hamiltonian of [arXiv:2209.02589].…
Iterative Interpolation Schedules for Quantum Approximate Optimization Algorithm
Anuj Apte, Shree Hari Sureshbabu, Ruslan Shaydulin +5
Quantum Approximate Optimization Algorithm (QAOA) is a promising quantum heuristic with empirical evidence of speedup over classical state-of-the-art for some problems. QAOA uses a…