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). Hiding is usually accomplished 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 minimum number of transactions from which items need to be removed to consider all 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 warm-start QAOA through biased superposition coupled with a new mixer as an alternative to uniform superposition. We further 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 examine thirty-five problem instances and conduct twenty-five runs with different starting parameter values for each problem instance. At least two of the twenty-five runs for every problem instance result in the optimal solution when uniform superposition is used. The corresponding number for biased superposition is at least nine runs. Our findings demonstrate that quantum computers in general, and QAOA in particular, can be effectively applied to a long-studied problem in data privacy.
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). Hiding is usually accomplished 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 minimum number of transactions from which items need to be removed to consider all 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 warm-start QAOA through biased superposition coupled with a new mixer as an alternative to uniform superposition. We further 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 examine thirty-five problem instances and conduct twenty-five runs with different starting parameter values for each problem instance. At least two of the twenty-five runs for every problem instance result in the optimal solution when uniform superposition is used. The corresponding number for biased superposition is at least nine runs. Our findings demonstrate that quantum computers in general, and QAOA in particular, can be effectively applied to a long-studied problem in data privacy.
The benefits of sharing transactional data with upstream supply chain partners has been known for a long time. However, many retailers are still reluctant to share, and there is evidence that the extent of sharing would be greater if information sensitive to retailers is concealed before data are shared. In transactional data, sensitive information are typically frequent itemsets that can be hidden by deleting items belonging to the sensitive itemsets from transactions that support the itemsets. The problem of identifying the smallest set of transactions from which to delete items such that sensitive itemsets will be hidden can be formulated as a generalized set covering problem. Numerous classical approaches have been developed for solving this problem. We propose a new approach to solve this optimization problem using QAOA. In our preliminary experiments, we find optimal solutions for small problems (that use up to 32 qubits) by using simulators and real quantum computers even when we use only one layer of QAOA. Identifying properties of the optimization problem should further help in faster convergence towards the optimal solutions of the optimization problem.
Recent advances in quantum computing and the increasing availability of quantum hardware have substantially enhanced the practical relevance of quantum approaches to discrete optimization. Among these, the Quadratic Unconstrained Binary Optimization (QUBO) formulation provides a unifying modeling framework for a broad class of NP-hard problems and is naturally suited to quantum computing and quantum-inspired algorithms. Location science, network design, and logistics represent core application domains of discrete optimization, combining high practical impact with substantial computational challenges. In this work, we develop QUBO formulations for several fundamental problems in these domains, including a nonlinear integer formulation of the Discrete Ordered Median Problem (DOMP). Beyond their modeling relevance, these QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware. We further derive a tight bound for the penalty parameter ensuring equivalence between the QUBO formulation and its underlying integer program. Finally, we conduct a comprehensive computational study using QAOA, WS-QAOA, and classical heuristics for QUBO instances of the p-Median Problem and the Fixed-Charge Facility Location Problem (FCFLP), and introduce two effective warm-start strategies for WS-QAOA based on its linear programming relaxation.
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-k-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
Association rules mining (ARM) is one of the most important problems in knowledge discovery and data mining. Given a transaction database that has a large number of transactions and items, the task of ARM is to acquire consumption habits of customers by discovering the relationships between itemsets (sets of items). In this paper, we address ARM in the quantum settings and propose a quantum algorithm for the key part of ARM, finding frequent itemsets from the candidate itemsets and acquiring their supports. Specifically, for the case in which there are Mf(k) frequent k-itemsets in the Mc(k) candidate k-itemsets (${M}_{f}^{(k)}\ensuremath{\le}{M}_{c}^{(k)}$), our algorithm can efficiently mine these frequent k-itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity $O(\frac{k\sqrt{{M}_{c}^{(k)}{M}_{f}^{(k)}}}{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the error for estimating the supports. Compared with the classical counterpart, i.e., the classical sampling-based algorithm, whose complexity is $O(\frac{k{M}_{c}^{(k)}}{{\ensuremath{\epsilon}}^{2}})$, our quantum algorithm quadratically improves the dependence on both $\ensuremath{\epsilon}$ and Mc(k) in the best case when ${M}_{f}^{(k)}\ensuremath{\ll}{M}_{c}^{(k)}$ and on $\ensuremath{\epsilon}$ alone in the worst case when ${M}_{f}^{(k)}\ensuremath{\approx}{M}_{c}^{(k)}$.