BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jonathan Allcock

Jonathan Allcock appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phComputational ComplexityCryptography and SecurityData Structures and Algorithms

Catalog footprint

What is connected

7works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2025arXiv

QAOA-MaxCut has barren plateaus for almost all graphs

The QAOA has been the subject of intense study over recent years, yet the corresponding Dynamical Lie Algebra (DLA)--a key indicator of the expressivity and trainability of VQAs--remains poorly understood beyond highly symmetric instances. An exponentially scaling DLA dimension is associated with the presence of so-called barren plateaus (BP) in the optimization landscape, which renders training intractable. In this work, we investigate the DLA of QAOA applied to the canonical MaxCut, for both weighted and unweighted graphs. For weighted graphs, we show that when the weights are drawn from a continuous distribution, the DLA dimension grows as $Θ(4^n)$ almost surely for all connected graphs except paths and cycles. In the more common unweighted setting, we show that asymptotically all but an exponentially vanishing fraction of graphs have $Θ(4^n)$ large DLA dimension. The entire simple Lie algebra decomposition of the corresponding DLAs is also identified, from which we prove that the variance of the loss function is $O(1/2^n)$, implying that QAOA on these weighted and unweighted graphs all suffers from BP. Moreover, we give explicit constructions for families of graphs whose DLAs have exponential dimension, including cases whose MaxCut is in $\mathsf P$. Our proof of the unweighted case is based on a number of splitting lemmas and DLA-freeness conditions that allow one to convert prohibitively complicated Lie algebraic problems into amenable graph theoretic problems. These form the basis for a new algorithm that computes such DLAs orders of magnitude faster than previous methods, reducing runtimes from days to seconds on standard hardware. We apply this algorithm to MQLib, a classical MaxCut benchmark suite covering over 3,500 instances with up to 53,130 vertices, and find that, ignoring edge weights, at least 75% of the instances possess a DLA of dimension at least $2^{128}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming

Subset-Sum is an NP-complete problem where one must decide if a multiset of $n$ integers contains a subset whose elements sum to a target value $m$. The best-known classical and quantum algorithms run in time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value. Given any modulus $p$, our data structure can be constructed in time $O(n^2p)$, after which queries can be made in time $O(n^2)$ to the lists of subsets summing to any value modulo $p$. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums, an improvement on the best-known $O(2^{0.773n})$ classical running time. Incidentally, we obtain new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ classical and quantum algorithms for Subset-Sum, not based on the seminal meet-in-the-middle method. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem, we give faster classical and quantum algorithms with running time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{2n/5})$, respectively. For the more general modular problem, we give a classical algorithm that also runs in time $\tilde{O}(2^{n/2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient multi-qubit subspace rotations via topological quantum walks

The rotation of subspaces by a chosen angle is a fundamental quantum computing operation, with applications in error correction and quantum algorithms such as the Quantum Approximate Optimization Algorithm, the Variational Quantum Eigensolver and the quantum singular value transformation. Such rotations are usually implemented at the hardware level via multiple-controlled-phase gates, which lead to large circuit depth when decomposed into one- and two-qubit gates. Here, we propose a fast, high-fidelity way to implement such operations via topological quantum walks, where a sequence of single-qubit $z$ rotations of an ancilla qubit are interleaved with the evolution of a system Hamiltonian in which a matrix $A$ is embedded. The subspace spanned by the left or right singular vectors of $A$ with non-zero singular values is rotated, depending on the state of the ancilla. This procedure can be implemented in superconducting qubits, ion-traps and Rydberg atoms with star-type connectivity, significantly reducing the total gate time required compared to previous proposals.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Suppressing ZZ Crosstalk of Quantum Computers through Pulse and Scheduling Co-Optimization

Noise is a significant obstacle to quantum computing, and $ZZ$ crosstalk is one of the most destructive types of noise affecting superconducting qubits. Previous approaches to suppressing $ZZ$ crosstalk have mainly relied on specific chip design that can complicate chip fabrication and aggravate decoherence. To some extent, special chip design can be avoided by relying on pulse optimization to suppress $ZZ$ crosstalk. However, existing approaches are non-scalable, as their required time and memory grow exponentially with the number of qubits involved. To address the above problems, we propose a scalable approach by co-optimizing pulses and scheduling. We optimize pulses to offer an ability to suppress $ZZ$ crosstalk surrounding a gate, and then design scheduling strategies to exploit this ability and achieve suppression across the whole circuit. A main advantage of such co-optimization is that it does not require special hardware support. Besides, we implement our approach as a general framework that is compatible with different pulse optimization methods. We have conducted extensive evaluations by simulation and on a real quantum computer. Simulation results show that our proposal can improve the fidelity of quantum computing on $4{\sim}12$ qubits by up to $81\times$ ($11\times$ on average). Ramsey experiments on a real quantum computer also demonstrate that our method can eliminate the effect of $ZZ$ crosstalk to a great extent.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer

Quantum computing for the biological sciences is an area of rapidly growing interest, but specific industrial applications remain elusive. Quantum Markov chain Monte Carlo has been proposed as a method for accelerating a broad class of computational problems, including problems of pharmaceutical interest. Here we investigate the prospects of quantum advantage via this approach, by applying it to the problem of modelling antibody structure, a crucial task in drug development. To minimize the resources required while maintaining pharmaceutical-level accuracy, we propose a specific encoding of molecular dihedral angles into registers of qubits and a method for implementing, in quantum superposition, a Markov chain Monte Carlo update step based on a classical all-atom force field. We give the first detailed analysis of the resources required to solve a problem of industrial size and relevance and find that, though the time and space requirements of using a quantum computer in this way are considerable, continued technological improvements could bring the required resources within reach in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Shortcuts to Adiabaticity for Open Systems in Circuit Quantum Electrodynamics

Shortcuts to adiabaticity (STA) are powerful quantum control methods, allowing quick evolution into target states of otherwise slow adiabatic dynamics. Such methods have widespread applications in quantum technologies, and various STA protocols have been demonstrated in closed systems. However, realizing STA for open quantum systems has presented a greater challenge, due to complex controls required in existing proposals. Here we present the first experimental demonstration of STA for open quantum systems, using a superconducting circuit QED system consisting of two coupled bosonic oscillators and a transmon qubit. By applying a counterdiabatic driving pulse, we reduce the adiabatic evolution time of a single lossy mode from 800 ns to 100 ns. In addition, we propose and implement an optimal control protocol to achieve fast and qubit-unconditional equilibrium of multiple lossy modes. Our results pave the way for accelerating dynamics of open quantum systems and have potential applications in designing fast open-system protocols of physical and interdisciplinary interest, such as accelerating bioengineering and chemical reaction dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks

It has previously been shown that quantum nonlocality offers no benefit over classical correlations for performing a distributed task known as nonlocal computation. This is where separated parties must compute the value of a function without individually learning anything about the inputs. We show that giving the parties some knowledge of the inputs, however small, is sufficient to unlock the power of quantum mechanics to out-perform classical mechanics. This role of information held locally gives new insight into the general question of when quantum nonlocality gives an advantage over classical physics. Our results also reveal a novel feature of the nonlocality embodied in the celebrated task of Clauser, Horne, Shimony and Holt.

0 citations0 reviewsNo code linkedOpen access