Grover-based Ashenhurst-Curtis Decomposition Using Quantum Language Quipper

Published In

Quantum Information & Computation 2018

Document Type


Publication Date



Functional decomposition plays a key role in several areas such as system design, digital circuits, database systems, and Machine Learning. This paper presents a novel quantum computing approach based on Grover’s search algorithm for a generalized Ashenhurst-Curtis decomposition. The method models the decomposition problem as a search problem and constructs the oracle circuit based on the set-theoretic partition algebra. A hybrid quantum-based algorithm takes advantage of the quadratic speedup achieved by Grover’s search algorithm with quantum oracles for finding the minimum-cost decomposition. The method is implemented and simulated in the quantum programming language Quipper. This work constitutes the first attempt to apply quantum computing to functional decomposition


© Rinton Press

Persistent Identifier