Multi-Unary: a dense input encoding scheme for the quantum circuit model

Abstract

The choice of a given encoding scheme for the problem variables, represented by a set of input qubits of a quantum circuit, substantially influences its design, as well as the quantity and nature of quantum resources (qubits and gates) employed by it. Quantum programmers have access to a variety of encoding strategies, such as one-hot, binary, Gray, amplitude encoding, or Schmidt decomposition, but each of them allows encoding just a single value for each problem variable. This article introduces a novel encoding scheme based on one-hot encoding, termed Multi-Unary, which enables the representation of multiple values within the input qubits, hence the descriptor ‘dense encoding scheme.’ The application of Multi-Unary is demonstrated in the context of the graph coloring problem using Grover’s algorithm, although its applicability extends to a broader class of quantum algorithms. By increasing the informational density on the input qubits, the multi-unary encoding offers potential advantages in terms of circuit compactness and resource efficiency, while at the same time enables an output value to contain more than one solution to a problem. Given its simple implementation, it can even replace the one-hot encoding scheme.