Quantum Computers: Fewer Steps to Solve Problems

Scientists at the Infineon Technologies AG Munich have developed a new quantum protocol for tackling the binary rucksack problem, a computationally intensive task with significant implications for optimisation challenges. Laurin Demmler and Maximilian Hess propose a nested Amplitude Amplification protocol designed to mitigate the demanding circuit depths typically associated with Grover Adaptive Search (GAS). The core innovation lies in a strategy of partial amplification of the search space, performed on a subset of variables, before initiating a global GAS across the full problem instance. This approach aims to reduce the quantum resources, specifically the number of qubits and circuit operations, required to achieve optimisation, bringing practical quantum solutions closer to realisation.

Nested Amplitude Amplification enhances quantum rucksack problem solving

Simulations demonstrate a reduction of up to 20 per cent in the computational cost associated with improving an incumbent solution when utilising the nested Amplitude Amplification protocol, when compared to a baseline implementation of Grover Adaptive Search. This improvement is crucial as it extends the feasible scope of quantum optimisation, allowing researchers to simulate rucksack instances of sizes previously intractable using conventional statevector simulation methods. The binary rucksack problem, in its essence, involves selecting a subset of items, each with a weight and a value, to maximise the total value while adhering to a weight constraint. The search space grows exponentially with the number of items, making classical solutions increasingly difficult. The proposed protocol addresses this complexity by strategically dividing the decision tree inherent in the problem.

A key advancement towards applying quantum algorithms to complex, real-world problems, such as those encountered in supply-chain optimisation, logistics, resource allocation, and portfolio optimisation, has been made. The nested protocol’s effectiveness stems from its ability to exploit the problem’s structure. Further analysis revealed that the ‘Inner Iteration Finder’, a component responsible for optimising the partial amplification stage, successfully maximised the amplitude of the marked subspace. In quantum search algorithms, amplitude amplification increases the probability of measuring a desired solution. By effectively concentrating the probability amplitude onto the relevant solutions within the partially amplified subspace, the subsequent global search benefits from a more favourable starting point. Simulations utilising the Quantum Tree Generator, a novel method for creating initial quantum states with a bias towards feasible solutions, were vital in achieving these results. The Quantum Tree Generator constructs a superposition state where solutions that satisfy the rucksack’s weight constraint have a higher initial amplitude. This pre-conditioning further enhances the efficiency of the amplitude amplification process. The protocol’s effectiveness was particularly noticeable on specific rucksack instances exhibiting certain characteristics, suggesting a subtle relationship between problem structure and algorithmic performance; instances with a higher density of near-optimal solutions appeared to benefit more significantly from the nested approach.

Quantum computers, while still in their nascent stages of development, offer the potential for significant speedups over classical computers for certain computational tasks. However, the construction of stable and scalable quantum computers remains exceptionally difficult, particularly concerning qubit coherence and gate fidelity. The binary rucksack problem, a well-established benchmark in the field of combinatorial optimisation, was solved by employing this nested quantum technique. The choice of the rucksack problem is deliberate; its practical relevance and well-defined structure make it an ideal test case for evaluating quantum optimisation algorithms. Performance gains observed are specific to certain problem instances and depend on how the algorithm tailors itself to the problem’s structure. The nested approach demonstrably reduces the cost of improving a solution compared to baseline methods, but the extent of this reduction is influenced by the characteristics of the specific rucksack instance it solves. This highlights the importance of problem-specific algorithm design in quantum computing.

Deliberately dividing the problem’s search space into stages reduces computational effort when seeking improved solutions to the binary rucksack problem, a defining feature of the new protocol. This contrasts with standard Amplitude Amplification methods that attempt to amplify the entire search space simultaneously. This staged approach allows for a more efficient allocation of quantum resources, particularly in the context of Noisy Intermediate-Scale Quantum (NISQ) devices, which are limited in the number of qubits and the depth of circuits they can reliably execute. Larger rucksack instances than previously possible with conventional techniques were explored through simulations utilising the Quantum Tree Generator, pushing the boundaries of what can be simulated classically. Partial amplification creates a biased starting point for a subsequent global search, effectively narrowing the search space and increasing the probability of finding optimal or near-optimal solutions. The tunable depth at which the decision tree is split represents a key parameter, allowing researchers to balance the complexity of the partial amplification stage with the effectiveness of the global search.

The implications of this work extend beyond the binary knapsack problem itself. The nested Amplitude Amplification strategy could be adapted to other combinatorial optimisation problems, potentially offering a pathway towards developing practical quantum algorithms for a wider range of applications. Future research will focus on exploring the relationship between problem structure and algorithmic performance in greater detail, as well as investigating methods for automatically tuning the parameters of the nested protocol to optimise its performance for different problem instances. Furthermore, implementing this protocol on actual quantum hardware will be crucial to assess its performance in a realistic setting and to identify potential challenges related to qubit coherence and gate errors.

The researchers demonstrated a new nested Amplitude Amplification protocol that reduces the computational cost of finding better solutions to the binary knapsack problem. By strategically dividing the problem’s search space, this method requires less complex quantum circuits than standard approaches, which is important for current quantum computers. Simulations using instances intractable for conventional methods showed the protocol’s effectiveness, particularly for certain knapsack problems. The authors intend to further investigate how problem structure affects performance and to optimise the protocol’s parameters for various instances.