Quantum computing is a fast-growing technology, currently progressing by the minute. The technology uses quantum entanglement and superposition to process information. Where classical computers operate using bits – which can exist in one of two possible states, either a 0 or a 1 – quantum computers are built from quantum bits, or ‘qubits’, which can be both a 0 and a 1 at the same time.

When multiple qubits are entangled together, they can collectively exist in many different states simultaneously. This allows them to present a single-condensed image of the entire search space at once. Candidate solutions of deeply complex problems can be investigated or calculated all at once, in just a single go of the quantum program. As a result, quantum computers excel in fishing out answers from an immense number of candidate solutions.

In the case of classical computers, to obtain an answer to a search problem, algorithms need to trawl through vast datasets of possibilities. To get a definite answer, the entire dataset of candidates must be analysed bit by bit. The amount of time taken to search through the complete set of candidates would increase linearly with the number of items it contains, making the operation both time-consuming and energy intensive.

However, with their ability to compute multiple data simultaneously, quantum search algorithms can carry out an operation that applies to all solution candidates at once. This makes them significantly faster and more energy efficient, especially as the size of the dataset increases.

As part of their inner workings, both classical and quantum search algorithms need to access an ‘oracle’. In Greek mythology, an oracle is someone who, when summoned, speaks wisely,

knowledgably, and infallibly, though sometimes ambiguously. People would visit them to get seemingly authoritative answers to their questions. Yet even though they were allowed to ask multiple questions, each answer was considerably expensive.

In computer science, an oracle inherits the same properties: a query to the oracle is expensive; multiple queries are possible; and the answers, while seemingly authoritative, may be ambiguous. For example, in the case of a search problem, the oracle can say whether a particular candidate solution is an actual solution or not. This is a simple search question, but what about an all-encompassing question? For example, does the problem have a solution after all? This question is in the category of decision problems.

In the present study, a pair of researchers in Saudi Arabia, Dr Marius Nagy at Prince Mohammad Bin Fahd University, together with Dr Naya Nagy at Imam Abdulrahman Bin Faisal University, tested the ability of quantum computers to determine, that is decide, whether a particular class of computational problems are solvable. They demonstrate that quantum computers not only outperform classical computers, but can provide more nuanced answers.

In particular, it is only quantum algorithms that sometimes can recognize the situation where a problem has no solution. In this case, the algorithm can answer ‘No’ with certainty, even after just a single query of the oracle. In contrast, classical computers are unable to discover the absence of solutions unless they trawl the entire search space, no matter how simple the problem.

Additionally, when the question really refers to borderline situations, quantum computers can give an honest ‘I do not know’, or ‘undecided’ answer. Again, the classical counterpart is unable to mimic this type of evaluation. As such, the quantum oracle proves to be broader and richer in the decision answers it provides.

Through their research, the duo has shown immediate applications of this paradigm on ‘NP-complete’ problems, short for ‘nondeterministic polynomial-time complete’ problems. NP problems have two variants: finding the actual solution, or deciding whether a solution exists.

The second variant is important for quick decisions. Imagine that a quantum oracle can quickly say, at one invocation, that no solution exists. This information can then spare the decision maker the entire effort of searching for a solution. It can then free up resources to redefine the problem and search space to find a better option.

One classic example of an NP-problem is called the ‘travelling salesman problem’, or TSP. Here, a salesman is given a list of cities they need to visit, along with the distances between each pair of cities. In the optimization version of the problem, the salesman must find the shortest possible route that visits each city exactly once, before returning to their home city.

As a simple example, imagine that a salesman in London needs to travel to Paris, New York, and Boston, before returning home. In theory, they could travel to New York first before flying back across the Atlantic to Paris, and then back again to Boston. Clearly, however, it would be far more efficient to travel to Paris first, then visit both American cities in a single return trip across the Atlantic.

Yet in the decision version of TSP, the salesman is also given a distance, and needs to determine whether or not a route exists that allows them to travel to each city within that distance. In this case, if the salesman needed to complete the route in under 12,000 kilometres, any route which involves a single return trip across the Atlantic would satisfy all their requirements.

However, if they instead needed to complete the trip in under 10,000 kilometres, there is no possible route which can satisfy all their requirements. As a result, a decision algorithm working on this problem would need to state unambiguously that no viable route exists.

In real life, far more complex versions of this problem can be found across a wide array of scenarios. For example, a company providing on-site technical support might need to determine whether or not their technicians can visit all of their customers within working hours, given the locations of their customers.

Alternatively, a team responding to a natural disaster may need to determine if they have enough time to visit all critical sites before returning to base, ensuring they are ready to respond to other emergencies. In either case, as the number of locations increases, the number of possible routes can quickly become vast.

When making a decision on an NP-complete problem, the oracle has to quickly get an overview of the vast data set, and conclude whether the solution does indeed lie hidden somewhere in the search space, or if the space is devoid of all solutions.

Dr Nagy and Nagy’s results show that the quantum improvement can be implemented even with simple gates and measurements, such as the Hadamard gates and computational basis measurements. The quantum computer still has a better chance of discriminating between problems with solutions and those without, when compared with the best separation achieved by a classical decision algorithm.

If the decision algorithm is required to make no mistakes, the quantum solution can be implemented with a technique called ‘positive operator-valued measurement’. Here, the quantum oracle may answer yes, no, or undecided, but with full correctness. This behavior would be impossible to implement using classical algorithms.

The inherent probabilistic nature of quantum mechanics seems to be at the heart of the advantage that quantum computing exhibits over classical computation, in the context of deciding NP-complete problems based on a single oracle query.

The researchers found that quantum measurement strategies exist that may determine when no solution is available after accessing the oracle just once: something a classical algorithm can’t possibly achieve without first examining every possible solution.

Altogether, the duo’s analysis reveals deeper insights into the wealth of advantages offered by quantum deciders, compared with the classical decision algorithms still widely used today.

By showing that quantum techniques can improve sensitive and fast decisions, their results could encourage researchers to expand their use of quantum computing and unlock new access to its immense processing power. In turn, their insights may bring us a step closer to seeing the widespread use of quantum computers in our everyday lives.