Quantum Computer Calculations Become Far Cheaper with New Memory Technique

Researcher Danial Motlagh and Matthew Pocrnic, have detailed a new optimisation that substantially lowers the computational cost associated with quantum read only memory (QROM). This subroutine is a cornerstone of numerous quantum algorithms and currently represents a significant portion of the overall algorithmic overhead in most practical applications of quantum computers. Their findings demonstrate a reduction in the Toffoli cost, a critical metric for evaluating the efficiency of quantum circuits, by approximately 50 percent in scenarios where the number of available qubits is limited. The advancement effectively diminishes the performance disparity between QROM implementations utilising readily available ‘dirty’ qubits, those susceptible to errors, and those employing ideal ‘clean’ qubits, paving the way for more efficient quantum computations.

SelectCopy architecture halves Toffoli cost in quantum read only memory

The Toffoli cost, representing the number of multi-controlled NOT (Toffoli) gates required, is a primary determinant of the complexity and resource requirements of quantum algorithms. Traditionally, the Toffoli cost of QROM has been a significant obstacle to scalability. The researchers have successfully reduced this cost from approximately 2N/λ to (1 + 1/b)N/λ, representing a decrease of around 50 percent. Here, N denotes the number of bitstrings to be loaded, b represents the length of each bitstring, and λ signifies the number of available ‘dirty’ qubits. Achieving performance comparable to ‘clean-qubit’ QROM, which relies on qubits free from errors and thus requires substantial overhead for error correction, was previously unattainable when utilising readily available ‘dirty’ qubits. The optimisation centres around replacing the conventional “SelectSwap” architecture with a novel “SelectCopy” approach, and the introduction of a parametric method that allows for fine-tuning of QROM performance based on the available qubit resources.

QROM is a fundamental subroutine in a wide range of quantum algorithms, including those designed for searching databases, solving optimisation problems, and simulating quantum systems. Consequently, reducing its computational overhead has the potential to accelerate progress towards practical quantum computation. The replacement of the standard “SelectSwap” with “SelectCopy” lowered the overall cost from 2N/λ + 4b(λ-1) to 2N/λ + 2b(λ-1) + 2λ-6. This initial reduction is further enhanced by the parametric approach, which allows performance to be tailored to the specific constraints of the quantum hardware. For instance, when the number of elements N is significantly larger than b squared times λ squared, setting a parameter α equal to b becomes optimal, minimising the required resources. Graphical comparisons against prior art demonstrate an improvement factor exceeding ten for certain configurations, indicating a substantial potential for performance gains. However, it is crucial to note that these calculations currently assume ideal conditions and do not yet fully account for the significant overhead introduced by error correction, a necessity in real-world quantum hardware due to the inherent fragility of quantum states. Future research will focus on mitigating these practical limitations and integrating error correction schemes into the optimised QROM architecture.

Cost reductions in quantum read only memory favour limited qubit systems

Quantum computers hold the promise of revolutionising diverse fields, spanning medicine, materials science, finance, and artificial intelligence. However, realising this potential is contingent upon the efficient management of limited computational resources. Table lookup, a fundamental operation in many quantum algorithms and known as quantum read only memory or QROM, has long been a significant bottleneck. Accessing data stored in a quantum table requires complex manipulations of quantum bits, or qubits, and the associated gate operations contribute substantially to the overall computational cost. This delivers a valuable advance for practical quantum computing, as the improvements are most pronounced when qubit availability is limited. The optimisation effectively narrows the performance gap between quantum systems utilising readily available, imperfect qubits, known as ‘dirty’ qubits, and those employing ideal, error-free qubits, which are currently expensive and challenging to maintain. A resulting reduction in computational cost of approximately 50 percent in constrained scenarios expands the possibilities for complex quantum calculations, particularly for near-term devices with restricted qubit counts.

The significance of this work lies in its potential to make quantum algorithms more feasible on near-term quantum hardware. Current quantum computers are limited in the number of qubits they possess, and these qubits are also prone to errors. The optimisation presented by Motlagh and Pocrnic addresses both of these challenges by reducing the number of qubits required to implement QROM and by improving performance even when using imperfect qubits. The parametric nature of the approach allows quantum computer scientists to adapt the QROM implementation to the specific characteristics of their hardware, maximising performance within the given constraints. Furthermore, the reduction in Toffoli cost translates directly to a reduction in circuit depth, which is a crucial factor in mitigating the effects of decoherence, the loss of quantum information due to interactions with the environment. By reducing circuit depth, the optimised QROM implementation increases the probability that a quantum computation will succeed before the qubits lose their coherence. This is particularly important for complex algorithms that require a many number of gate operations. The research provides a crucial step towards building practical and scalable quantum computers capable of tackling real-world problems.

The researchers successfully optimised a key subroutine in quantum algorithms, known as quantum read only memory, reducing its computational cost by approximately 50 per cent in scenarios with limited qubits. This matters because it makes complex quantum calculations more feasible on current quantum hardware, which is constrained by both qubit number and the presence of errors. The optimisation narrows the performance gap between imperfect and ideal qubits, improving efficiency when using readily available resources. The authors demonstrated a parametric family of methods to tailor the implementation to specific hardware constraints, further enhancing performance.