43 citations · 179 across the 19 of their papers we have counts for
24 papers
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…
Prove2Me: An Open Collaborative Platform for Scaling Math Formalization
Shuze Chen, Kunal Marwaha, Xiaoyang Lu +2
Proof assistants such as Lean 4 promise the paradigm of formally verified mathematics, but large-scale formalization projects have faced major barriers to entry, including the need…
The QAOA on the ring of disagrees
Kunal Marwaha
We study the performance of symmetric local algorithms finding large cuts on the cycle graph. Such algorithms that cannot see the whole graph at depth p cut at most a (2p+1)/(2p+2)…
A complexity phase transition at the EPR Hamiltonian
Kunal Marwaha, James Sud
We study the computational complexity of 2-local Hamiltonian problems generated by a positive-weight symmetric interaction term, encompassing many canonical problems in statistical…
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…
An Exact Algorithm for the Unanimous Vote Problem
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha +2
Consider independent, biased coins, each with a known probability of heads. Presented with an ordering of these coins, flip (i.e., toss) each coin once, in that order, until we…
On the Complexity of Decoded Quantum Interferometry
Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu +1
We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization. First, we show that the algorithm resists classical simulation st…
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].…
Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs
Kunal Marwaha, Adrian She, James Sud
We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We…
Quantum Merlin-Arthur with an internally separable proof
Roozbeh Bassirian, Bill Fefferman, Itai Leigh +2
We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP NEXP. This gives a new route to prove…
Superposition detection and QMA with non-collapsing measurements
Roozbeh Bassirian, Kunal Marwaha
We prove that QMA where the verifier may also make a single non-collapsing measurement is equal to NEXP, resolving an open question of Aaronson. We show this is a corollary to a mo…
Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
Antares Chen, Neng Huang, Kunal Marwaha
We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sell…
Quantum Merlin-Arthur and proofs without relative phase
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
We study a variant of QMA where quantum proofs have no relative phase (i.e. non-negative amplitudes, up to a global phase). If only completeness is modified, this class is equal to…
A useful inequality of inverse hyperbolic tangent
Kunal Marwaha
We prove an inequality related to arctanh, resolving a conjecture of Gu and Polyanskiy [arXiv:2303.14689].
On the power of nonstandard quantum oracles
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
We study how the choices made when designing an oracle affect the complexity of quantum property testing problems defined relative to this oracle. We encode a regular graph of even…
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu +1
We study random constraint satisfaction problems (CSPs) in the unsatisfiable regime. We relate the structure of near-optimal solutions for any Max-CSP to that for an associated spi…
Non-Convex Optimization by Hamiltonian Alternation
Anuj Apte, Kunal Marwaha, Arvind Murugan
A major obstacle to non-convex optimization is the problem of getting stuck in local minima. We introduce a novel metaheuristic to handle this issue, creating an alternate Hamilton…
Fair allocation of a multiset of indivisible items
Pranay Gorantla, Kunal Marwaha, Santhoshini Velusamy
We study the problem of fairly allocating a multiset of indivisible items among agents with additive valuations. Specifically, we introduce a parameter for the numb…
QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz +1
Understanding the best known parameters, performance, and systematic behavior of the Quantum Approximate Optimization Algorithm (QAOA) remain open research questions, even as the a…
The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
Joao Basso, Edward Farhi, Kunal Marwaha +2
The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth .…
Bounds on approximating Max XOR with quantum and classical local algorithms
Kunal Marwaha, Stuart Hadfield
We consider the power of local algorithms for approximately solving Max XOR, a generalization of two constraint satisfaction problems previously studied with classical and quant…
An explicit vector algorithm for high-girth MaxCut
Jessica K. Thompson, Ojas Parekh, Kunal Marwaha
We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on -regular graphs of girth . For every and $k \geq…
Classical algorithms and quantum limitations for maximum cut on high-girth graphs
Boaz Barak, Kunal Marwaha
We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of cl…
Local classical MAX-CUT algorithm outperforms QAOA on high-girth regular graphs
Kunal Marwaha
The -stage Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but i…