Innsbruck, 28.01.2025 – After recently presenting the most efficient implementation for quantum algorithms, such as the Quantum Fourier Transform, on a linear chain, ParityQC now introduces Parity Twine. The Parity Twine method sets a new world record in optimizing the two crucial metrics of gate count and circuit depth. It outperforms all known state-of-the-art methods for implementing prominent quantum algorithms across a wide range of quantum hardware, including linear, square grids, hexagonal, ladder and all-to-all connected devices.
In the past few years, the field of quantum computing experienced significant advancements, to the point that current quantum devices can perform specialized tasks just as successfully as state-of-the-art classical computers. One of the significant challenges currently hindering the development of this technology is the implementation of algorithms on different hardware platforms. Quantum hardware systems have a sparse structure, where the connectivity between qubits required for the successful implementation of algorithms is often challenging. This means that implementations of complex (multi-body) quantum operations are often infeasible or require costly operations such as SWAP gates or qubit shuttling.
A group of physicists from ParityQC and the University of Innsbruck have now presented a breakthrough invention that allows to overcome this challenge. In the paper “Connectivity-aware Synthesis of Quantum Algorithms”, the authors (Florian Dreier, Christoph Fleckenstein, Gregor Aigner, Michael Fellner, Reinhard Stahn, Martin Lanthaler and Wolfgang Lechner) introduce a general method for the implementation of quantum algorithms that optimizes both gate count and circuit depth, the two most crucial metrics. The novel approach is shown to outperform all known state-of-the art methods for implementing prominent quantum algorithms across a wide range of quantum hardware, including linear, square grids, hexagonal, ladder and all-to-all connected devices.
The breakthrough invention is based on the ParityQC Architecture. The ParityQC team recently introduced a method named parity label tracking in the paper “Swap-less implementation of Quantum Algorithms”, as a successful technique to implement established algorithms with reduced gate count and circuit depth. Every physical qubit carries a logical parity label which can be altered by Clifford operations. By tracking these labels throughout a circuit, it is possible to understand the corresponding information flow, which enables the design of efficient quantum algorithms. In the new paper “Connectivity-aware Synthesis of Quantum Algorithms”, this approach is extended by connectivity-adapted CNOT based building blocks, called Parity Twine chains. These Parity Twine chains distribute quantum information between qubits, introducing quantum entanglement at the same time. For linear nearest-neighbor (LNN) systems, these chains are composed of sequences of paired CNOT gates, whereas in systems with different connectivity requirements, these pairs can be simplified to single CNOT gates. The authors present a generic construction recipe to implement quantum algorithms on specific hardware, demonstrating the efficiency of the approach in five different exemplary platforms: linear nearest-neighbor (LNN) systems, all-to-all connected systems, square grids, heavy hexagon and ladder devices. The method is shown to be highly effective – and in fact outperform current state-of-the-art approaches – for the implementation of two of the most prominent quantum algorithms: the Quantum Fourier Transform (QFT) and the Quantum Approximate Optimization Algorithm (QAOA).
“Our leap in performance with Parity Twine shows that through our quantum architecture approach, hardware development will go hand in hand with software development to achieve world-record results.” – Univ.-Prof. Dr. Wolfgang Lechner, Co-CEO at ParityQC and professor at the University of Innsbruck
Key points of the discovery:
– World-record efficiency. The ParityQC Architecture separates the physical connectivity from the logical connectivity. The grand challenge in co-design is how to run quantum algorithms most efficiently on given hardware connectivities. Parity Twine works for all connectivities (from linear to all-to-all) and outperforms all other state-of-the-art implementations with respect to both runtime and gate count.
– Proven optimality in specific cases. The authors rigorously demonstrate the optimality of the novel approach for certain cases, pushing the gate count and circuit depth of the implementation strategy to the theoretically possible minimum.
– Connectivity-aware algorithm design. The authors provide a generic framework for constructing generator CNOT circuits that adapt to different connectivity layouts, demonstrating that quantum algorithms can be efficiently implemented even on hardware with sparse connectivity.
– Specific examples for performance gains in QAOA and QFT. The application of the novel method to the Quantum Approximate Optimization Algorithm (QAOA) and Quantum Fourier Transform (QFT) results in a significant reduction in gate counts and circuit depths compared to existing algorithms, across different platforms.
The paper “Connectivity-aware Synthesis of Quantum Algorithms” is now available for peer review.
About ParityQC
ParityQC is the only quantum architecture company worldwide. The company’s focus is on developing blueprints and operating systemsfor quantum computers. ParityQC collaborates with hardware partners all over the world to jointly build highly scalable quantum computers, for applications ranging from solving optimization problems on NISQ devices to general-purpose, error-corrected quantum computing.
About the Lechner research group “Quantum Computing” at the University of Innsbruck
The Lechner research group at the University of Innsbruck is dedicated to theoretical quantum physics with the aim to solve computationally challenging problems efficiently in near-term quantum devices. The focus is research of coherent adiabatic and non-adiabatic processes, applications in machine learning and optimization problems as well as the investigation of implementations in different next-generation qubit platforms.
