Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .
We study the problem of maximizing a complex-valued quadratic form over the
Kth roots of unity. We show that when the objective matrix
Q⋆∈Cn×n of the quadratic has rank
r, the global maximizer belongs to a candidate set of size
O(rn2r−1). This set can be constructed deterministically in
O(rn2r+1) time by enumerating the vertices of a hyperplane arrangement in
R2r. The algorithm is embarrassingly parallel; with~
P processors, the time complexity drops to
O(rn2r+1/P). For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-
r matrix, we prove that applying our framework to a spectral truncation yields a multiplicative
(1−O(∥H∥2/δ⋆))-approximation guarantee, where
δ⋆ denotes the eigengap of the underlying rank-
r matrix and
H represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling
S≥O(1/εr−1) candidates achieves a
(1−ε)cos2(π/K)-approximation of the optimal rank-
r solution with high probability. Crucially, this sample size is entirely independent of
n, reducing the overall runtime to
O(S⋅n2). Computational experiments on synthetic benchmarks and large-scale graphs for \textsc{Max-3-Cut} confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where
n≥106.
We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions
⊂{0,1}n, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients and the right-hand side value in integer is considered as a candidate for a valid inequality. The validity of the linear inequality is determined by solving a conic relaxation of a subproblem such as the doubly nonnegative relaxation, under the assumption that an upper bound for the unknown optimal value of the problem is available. Moreover, the candidates generated for the multiple cutting inequalities are tested simultaneously for their validity in parallel. Preliminary numerical results on 60 quadratic unconstrained binary optimization problems with a simple implementation of the successive cutting inequalities using an 8- or 32-core machine show that the exact optimal values are obtained for 70\% of the tested problems, demonstrating the strong potential of the proposed technique.