Frequent Itemset Hiding using QAOA

Sharing transactional data with upstream supply-chain partners has long been recognized as beneficial to all involved. Yet many retailers remain reluctant to share for fear of divulging sensitive information. Evidence suggests that more retailers would be willing to share if retailer-sensitive information is concealed prior to sharing. In transactional data, such sensitive information often takes the form of frequent itemsets (referred to as sensitive itemsets). This is often done by removing appropriate items from selected transactions that support (contain) the sensitive itemsets. One well-studied question in this domain involves the identification of the fewest number of transactions from which items need to be deleted to consider the sensitive itemsets hidden. This can be formulated as a generalized set covering problem and is known to be NP-Hard. We propose a QAOA-based quantum algorithm to solve the sensitive itemset hiding problem. As QAOA targets quadratic unconstrained binary optimization (QUBO) problems, we first show how to convert our constrained formulation into an Ising representation that resembles a QUBO problem. We then exploit the polyhierarchical structure inherent in our problem to bias superposition and warm-start QAOA instead of relying on uniform superposition that is typically employed. We also derive closed-form expressions for the weights of the terms in the Ising formulation; these can be coded directly, thereby saving substantial computational effort. We demonstrate the effectiveness of our heuristic through a series of experiments.  We almost always obtain optimal solutions, with the biased initialization reducing the search space required to find the best answer substantially. This effect becomes more pronounced as the number of layers increases. In sum, we illustrate that quantum computers in general, and QAOA in particular, can be applied effectively to a long-studied data-privacy problem and could generalize to other applications that reduce to set covering.