Good choices from fewer qubits: new scheme solves optimisation problems efficiently

Optimisation problems, such as minimising cost involved for facility allocation, could be solved with less quantum resources using an approach proposed by CQT researchers.

Encountered in industries from supply chain management to banking, optimisation problems that tax classical computers are a promising target for quantum computing to have an impact. A CQT team led by Principal Investigator Dimitris Angelakis has proposed algorithms that could bring that impact forward.

Researchers previously expected to need much bigger quantum computers than available today to achieve speed-ups in solving real-world problems, which can involve as many as 10,000 variables.

Dimitris and his team describe in a 4 May paper in the journal Quantum a scheme that makes more efficient use of a quantum computer’s bits (qubits).

CQT PhD student Benjamin Tan, who is first author of the paper, says, “Our encoding scheme lets us use fewer qubits to solve bigger problems, allowing us to solve real-world problems on existing or near-term quantum devices.” Benjamin and Dimitris, who is also an Associate Professor at the Technical University of Crete, co-authored the paper with Marc-Antoine Lemonde, Supanut Thanasilp and CQT alumnus Jirawat Tangpanitanon.

Optimisation with fewer qubits

Solving optimisation problems involves finding a ‘best choice’ among many options, by some measure you define. The researchers’ scheme solves an optimisation problem known as the quadratic unconstrained binary optimisation (QUBO) problem. QUBO problems have binary variables that have only yes or no answers. Solving the problem would mean finding the best combination of yes and no.

Take a facility allocation QUBO problem for example. The binary variables could represent the many potential locations where an energy provider can build a power plant – either building a plant at location x or not building a plant. These decisions are influenced by a number of factors such as the cost of building the plant at a given location, the cost of transporting the energy from the plant to the grid, the availability of relevant resources in the area, the availability of energy storage and many others. Given a certain number of plants to build, the business would want to find the optimal locations at which the plants should be built to maximise output and minimise cost.

In standard quantum approaches to tackling such problems, such as quantum annealing or the quantum approximate optimisation algorithm (QAOA), each classical variable is represented by a qubit on a quantum computer. Problems quickly scale beyond the resources available, given today’s working quantum computers have only tens of qubits and industrial problems have of the order of tens of thousands variables.

Dimitris’ team take a fundamentally different approach, splitting their classical variables across register qubits and ancilla qubits. In the power plant example, the register qubits might encode a map of locations, and the ancilla qubits whether a plant should be placed at a given location or not. For N locations in a facility allocation problem, at the best case, only log₂(N) qubits is needed, allowing for an exponential reduction in qubits required.

In their paper, the researchers demonstrated their scheme by solving a randomly generated 64-variable QUBO problem using only seven qubits. Six qubits are enough to construct the map, where the 2⁶ states of the register qubits – 000000, 000001, 000010 and so on – are used as addresses for the classical variables. Looking at each of the map addresses is done via probing the ancilla qubit whose value would indicate if that variable should be given a “yes” or a “no”.

Using a hybrid quantum-classical approach, a classical optimiser was used to tune the parameters of a quantum circuit, allowing the quantum computer to arrive at a solution. The researchers wrote the code of their scheme using Python and Qiskit, a package developed by IBMQ to simulate quantum circuits. The convergence to the best solution for the 64-variable problem was quite good in spite of only using seven and not 64 qubits.

Improving solutions using correlations

The researchers also showed how adding additional qubits to selectively encode possible classical correlations between variables, for problems with specific structures, could yield better solutions while only adding a polynomial overhead on the number of qubits required. Using this approach, the researchers were able to find approximate solutions to a 42-variable Max-Cut problem with strong correlations, a specific case of a QUBO problem, with just eight qubits.

“One benefit of our encoding scheme is the flexibility to decide the best way of grouping your variables based on the number of qubits available,” says Benjamin.

As next steps, the researchers hope to further enhance the performance of the encoding scheme to compete alongside state-of-the-art classical algorithms, with a view to outperforming classical computers in the future. The typical size of problems classical computers struggle with is of the order of tens of thousands classical variables, which using the team’s algorithms could be within reach of near-term quantum computers. The team plans to collaborate with industrial partners to apply their approach to use cases including route optimisation in supply chain and financial optimisation problems.