Researchers Analyse Quantum Circuits and Generate Bounds on 2,000 Graphs

A new neurosymbolic framework, SCALAR, automates conjecture and reasoning within quantum circuit analysis, developed by Sean Feeney at Texas A&M University and colleagues. Applying SCALAR to 82 MaxCut instances and extending the analysis to 2,000 randomly generated graphs utilises a CUDA-Q tensor network simulator to scale experiments to instances of up to 77 qubits. The framework generates conjectured bounds linking optimal QAOA parameters to graph invariants, recovers known relationships and parameter transfer phenomena, and identifies correlations between graph structure and optimisation landscapes, potentially accelerating progress in quantum algorithm design and analysis.

Scaling SCALAR unlocks analysis of 77-qubit circuits via informed conjecture refinement

Experiments utilising SCALAR now scale to 77 qubits, a substantial increase from previous methods limited to smaller instances. This scaling is achieved through a novel integration of quantum simulation, symbolic conjecture generation, and large language model (LLM) interpretation, enabling the analysis of more complex quantum circuits previously intractable due to the exponential growth of computational demands with qubit number. Prior approaches to quantum algorithm analysis often relied on either exhaustive simulation, limited by qubit count, or heuristic methods lacking rigorous guarantees. SCALAR bridges this gap by systematically exploring the parameter space of quantum circuits and formulating testable hypotheses about their behaviour. The CUDA-Q tensor network simulator, employed within SCALAR, represents a significant advancement in efficiently modelling quantum systems, particularly for circuits with a moderate number of qubits. Tensor networks provide a compact representation of the quantum state, reducing memory requirements and computational complexity compared to traditional methods like state vector simulation. SCALAR successfully predicted optimal parameters, γ∗ and β∗, from just four graph invariants across graphs sharing a structural fingerprint, revealing a predictable link between problem structure and quantum algorithm performance. This suggests that the complexity of optimising quantum circuits can be significantly reduced by leveraging inherent properties of the problem instance.

Analysis of 82 MaxCut instances, sourced from the MQLib benchmark dataset, a standard resource for evaluating quantum algorithms on combinatorial optimisation problems, alongside 2,000 randomly generated graphs spanning regular, Erdos-Renyi, Barabasi-Albert, and Watts-Strogatz topologies, revealed these links. The MaxCut problem involves partitioning the nodes of a graph into two sets such that the number of edges crossing the partition is minimised. This is a classic NP-hard problem, making it an ideal candidate for exploring the potential advantages of quantum computation. The four graph topologies employed represent diverse network structures, allowing for a comprehensive assessment of SCALAR’s generalizability. Unlike traditional methods which discard failed conjectures, the system’s iterative approach treats conjecture violations as valuable signals, guiding further exploration and refinement of hypotheses about quantum circuit behaviour. This is achieved through a feedback loop where the LLM interprets the results of quantum simulations and proposes modifications to the symbolic conjectures. Integration with the CUDA-Q tensor network simulator, a tool for efficiently modelling quantum systems, facilitated this achievement. When examining graphs with shared characteristics, optimal parameters for the Quantum Approximate Optimisation Algorithm, γ∗ and β∗, can be determined by just four readily calculated graph invariants: node count, average degree, chromatic number, and maximum independent set size. However, these findings currently hold only for circuits with a depth of two QAOA rounds, and scaling to more complex, practically relevant problems remains a substantial challenge. The chromatic number represents the minimum number of colours needed to colour the vertices of a graph such that no two adjacent vertices share the same colour, while the maximum independent set size denotes the largest set of vertices in a graph, no two of which are adjacent. These invariants provide a concise characterisation of the graph’s structure, enabling SCALAR to identify patterns and predict optimal QAOA parameters.

Linking graph topology to QAOA parameter optimisation via automated hypothesis creation

Automated conjecture generation promises to accelerate progress in quantum algorithm design, a field currently reliant on painstaking manual analysis and informed guesswork. The Quantum Approximate Optimisation Algorithm (QAOA) is a prominent hybrid quantum-classical algorithm designed to find approximate solutions to combinatorial optimisation problems. However, determining the optimal parameters for QAOA remains a significant challenge, often requiring extensive numerical optimisation. SCALAR offers a powerful new tool for this task by linking graph structure to optimal parameters for the Quantum Approximate Optimisation Algorithm, though its current reliance on identifying shared ‘structural fingerprints’ presents a limitation. The ‘structural fingerprint’ refers to the set of graph invariants used by SCALAR to characterise the graph’s topology. While effective for graphs with similar structures, this approach may struggle with highly diverse or complex graphs. Despite this, SCALAR’s contribution to quantum algorithm design remains significant, particularly when considering its ability to identify patterns within known graph types. This new framework successfully automates the process of generating potential improvements for quantum algorithms by combining quantum simulation, symbolic conjecture generation, and LLM-based interpretation, automating a process previously dominated by human intuition. The LLM plays a crucial role in translating the results of quantum simulations into human-readable conjectures and identifying potential relationships between graph invariants and QAOA parameters. Analysing graphs across four topologies, regular, Erdős, Rényi, Barabási, Albert, and Watts-Strogatz, generated conjectured bounds relating optimal QAOA parameters to graph invariants, including known relationships such as periodicity constraints on the phase separation parameter γ. These periodicity constraints arise from the inherent symmetries of the QAOA circuit and can significantly simplify the optimisation process. Experiments scaled to instances of up to 77 qubits reveal correlations between graph structural features and optimisation landscape properties, and demonstrate predictable optimal parameters from a small set of graph invariants for graphs sharing a structural fingerprint. Understanding the relationship between graph structure and the optimisation landscape is crucial for designing more efficient quantum algorithms and mitigating the effects of local optima.

The research team developed SCALAR, a new framework that automatically generates potential improvements for quantum algorithms by linking graph structure to optimal parameters. This is important because it automates a process previously reliant on human intuition, potentially accelerating the design of more efficient quantum algorithms. SCALAR analysed 82 MaxCut instances and 2,000 randomly generated graphs of up to 77 qubits, identifying correlations between graph features and optimisation landscapes. The authors note the system’s performance is currently limited by its reliance on identifying shared structural features within graph types.