#variational #QML #strikesback #discretely In the recent work (#link in the first comment) we show that adaptivity in variational quantum algorithms can give an exponential advantage over non-adaptive approaches. By framing circuit recompilation as a discrete optimization problem, we identify a setting where hybrid quantum–classical loops are not just helpful, but necessary. Big thanks to my collaborators — 𝗭𝗼ë 𝗛𝗼𝗹𝗺𝗲𝘀, for super-energising discussions and pushing this through, and Chukwudubem Umeano, for helping to compile this piece together. Careful, long read below ❗️ 𝗔𝗱𝘃𝗮𝗻𝘁𝗮𝗴𝗲 𝗳𝗼𝗿 𝗗𝗶𝘀𝗰𝗿𝗲𝘁𝗲 𝗩𝗮𝗿𝗶𝗮𝘁𝗶𝗼𝗻𝗮𝗹 𝗤𝘂𝗮𝗻𝘁𝘂𝗺 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 𝗶𝗻 𝗖𝗶𝗿𝗰𝘂𝗶𝘁 𝗥𝗲𝗰𝗼𝗺𝗽𝗶𝗹𝗮𝘁𝗶𝗼𝗻 The question of whether variational quantum algorithms really need the hybrid quantum–classical loop has been a matter of debate in the last two years. The challenge comes from the ever-growing power of surrogating quantum models, and advances in classical simulation methods for problems with structure. This has been framed as a question to the community: 𝘋𝘰𝘦𝘴 𝘵𝘩𝘦 𝘱𝘳𝘰𝘷𝘢𝘣𝘭𝘦 𝘢𝘣𝘴𝘦𝘯𝘤𝘦 𝘰𝘧 𝘣𝘢𝘳𝘳𝘦𝘯 𝘱𝘭𝘢𝘵𝘦𝘢𝘶𝘴 𝘪𝘮𝘱𝘭𝘺 𝘴𝘪𝘮𝘶𝘭𝘢𝘣𝘪𝘭𝘪𝘵𝘺? Counterexamples exist, but most of them correspond to specific Boolean function learning or Shor-type algorithms in disguise. What we tried to do is to identify a setting where adaptivity appears more naturally, and relies on a different structure. The starting point is a simple observation: in classical discrete optimization, exponential separations between adaptive and non-adaptive search are known. If this logic carries over, then there should be quantum problems where adaptivity gives the same kind of exponential edge. In our preprint, we propose such a problem — quantum circuit recompilation. The task is to recover a “hidden” circuit structure, starting with quantum data (a state) prepared with randomly placed T-gates (“puzzles”) embedded in partially random unitaries. The ansatz has the reverse structure, but we don’t know where the gates are, and there are exponentially many options. We show that discrete quantum optimizers can efficiently unravel these puzzles, finding the right locations with a quadratic number of circuit evaluations. In contrast, non-adaptive searches face an exponentially hard landscape: non-separable, highly entangled, and full of magic. Importantly, we also find that optimization remains feasible under noise, using finite-shot samplers, even as the solution space grows exponentially. This points to a very particular (and largely overlooked) role for discrete optimization in variational quantum algorithms. It also raises a bigger question: what new problems can benefit from this kind of adaptivity? While we remain open to new discoveries, we already see clear connections to fault-tolerant protocols with partial structure, and to blind quantum computing scenarios. Grateful for the support from EPSRC and the QCi3 Hub!
Very nice! I am quite shocked.
Thank you! A very interesting paper!
Applying quantum optics tools to advance quantum computing
2whttps://scirate.com/arxiv/2510.01154