QUBO Formulation and Quantum-inspired Verification of Deep Neural Networks

Background

The explosive growth in applications for deep neural networks (DNNs) is opposed by perturbations in their input data. For an application such as autonomous driving, a mild perturbation can have dire consequences. DNNs are also susceptible to adversarial attacks, making security a high priority. There are various verification techniques that are used to overcome these obstacles, exact verification being the most desirable yet prohibitively expensive option. Most approaches are also based on software algorithms running on deterministic digital computers which are limited by the looming end of Moore’s Law scaling. However, binarized neural networks with low memory size and access requirements can be combined with novel verification methods and hardware to achieve exact verification while circumventing the speed and cost pain points.

Description

Researchers at the University of California, Santa Barbara have developed a novel mode of verifying binarized neural networks that can be efficiently run on quantum and digital annealers. The neural network’s verification problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem which is then solved using Ising machines such as quantum and digital annealers. The QUBO problem verifies whether the neural network is robust against perturbations within a certain bound. This technique has been validated using simulated annealing and Gurobi, and has achieved successful experimental results on Digital and Quantum Annealer — binary neural networks with thousands of Boolean variables have been verified successfully on Digital Annealer. This invention forges a path toward enabling exact verification not just by algorithmic advances, but by building domain-specific hardware that will deploy these algorithms.

Advantages

  • Efficient exact verification of binarized neural networks that can be run on quantum and digital annealers
  • Low memory size and access requirements allow for smaller hardware

Applications

  • High-performance computation
  • Quantum computing
  • Ising computing
  • Trustworthy artificial intelligence (AI)
    • Safe autonomous systems
  • Finance