Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers

Abstract

While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings.

arXiv comment11 pages, 2+1 figures, JPhys Complexity (invited perspective)

References in corpus (21)

• Quantum Simulation of Antiferromagnetic Spin Chains in an Optical Lattice
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Digitized adiabatic quantum computing with a superconducting circuit
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Onset of a Quantum Phase Transition with a Trapped Ion Quantum Simulator
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Nature's Way of Optimizing
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Quantum Optimization of Fully-Connected Spin Glasses
• Silicon quantum processor with robust long-distance qubit couplings
• Reachability Deficits in Quantum Approximate Optimization
• Extremal Optimization for Graph Partitioning
• Benchmarking the Quantum Approximate Optimization Algorithm
• On the Universality of the Quantum Approximate Optimization Algorithm
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
• Networks of non-equilibrium condensates for global optimization
• Extremal Optimization of Graph Partitioning at the Percolation Threshold
• The stochastic traveling salesman problem: Finite size scaling and the cavity prediction
• Phase Transition in Multiprocessor Scheduling