ORCA Computing discovers new algorithm for solving QUBO problems

Using only a small number of gates and qubits

ORCA Computing has released a paper describing a method of using a shallow, near-term quantum computer to solve the real-world ‘QUBO’ problem. Quadratic unconstrained binary optimisation or QUBO for short is a combinatorial optimisation problem with a wide range of applications from financial modelling to supply chain logistics. It’s well known to be an NP-hard problem and therefore challenging to solve on classical computers.

This breakthrough demonstrates that photonics platforms, and ORCA in particular are in serious contention for delivering the first demonstrations of quantum value, the point beyond quantum advantage where a quantum system is used for a real and commercially valuable problem.

This paper highlights two ground-breaking developments:

  1. It allows QUBO problems to be solved on near-term photonic ‘Boson sampling’ systems. It does this by demonstrating a mapping between the output states of this photonic machine and all possible QUBO-compatible binary sequences.
  2. It shows that even near-term, shallow and non-universal quantum systems, can be used for these types of problems without requiring a very large number of operations. This shows a clear path towards near-term quantum supremacy on a real-life system, such as ORCA’s PT-series (time-based photonic machine).

ORCA has also simulated this approach and compared it to existing QUBO solvers. They’ve found that the ORCA QUBO solver out-performs both existing classical methods (known as simulated annealing) as well as the D-wave quantum methods when applied to the ‘knapsack problem’ – a packing optimisation algorithm.

This novel method will be specifically suited to ORCA’s PT-series photonic quantum computing system. It uses ORCA’s proprietary quantum memory, along with optical fibre to solve quantum computing problems in a rack-mounted, portable and room temperature system.

ORCA is working with leading users of quantum computers to apply this system to real-world problems across ICT, Energy, Finance and Defence.

To read our notes and simulation code as an open-source resource, please see our GitHub page here.