Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNISQ Algorithm for Semidefinite Programming
88
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an NP-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for SDP. The classical optimization program of our NISQ solver is another SDP over a smaller dimensional ansatz space. We harness the SDP based formulation of the Hamiltonian ground state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex, can be solved in polynomial time with the number of ansatz parameters and every local minimum is a global minimum. Further, we demonstrate the potential of our NISQ SDP solver by finding the largest eigenvalue of up to $2^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
rate research
Read More
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with $m$ constraint matrices, each of dimension $n$ and rank $r$, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time $O(mcdotmathrm{poly}(log n,r,1/varepsilon))$ given access to a sampling-based low-overhead data structure for the constraint matrices, where $varepsilon$ is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC 12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC 19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: $bullet$ Weighted sampling: assuming sampling access to each individual constraint matrix $A_{1},ldots,A_{tau}$, we propose a procedure that gives a good approximation of $A=A_{1}+cdots+A_{tau}$. $bullet$ Symmetric approximation: we propose a sampling procedure that gives the emph{spectral decomposition} of a low-rank Hermitian matrix $A$. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.
Semidefinite programming is an important optimization task, often used in time-sensitive applications. Though they are solvable in polynomial time, in practice they can be too slow to be used in online, i.e. real-time applications. Here we propose to solve feasibility semidefinite programs using artificial neural networks. Given the optimization constraints as an input, a neural network outputs values for the optimization parameters such that the constraints are satisfied, both for the primal and the dual formulations of the task. We train the network without having to exactly solve the semidefinite program even once, thus avoiding the possibly time-consuming task of having to generate many training samples with conventional solvers. The neural network method is only inconclusive if both the primal and dual models fail to provide feasible solutions. Otherwise we always obtain a certificate, which guarantees false positives to be excluded. We examine the performance of the method on a hierarchy of quantum information tasks, the Navascues-Pironio-Acin hierarchy applied to the Bell scenario. We demonstrate that the trained neural network gives decent accuracy, while showing orders of magnitude increase in speed compared to a traditional solver.
We apply semidefinite programming for designing 1 to 2 symmetric qubit quantum cloners. These are optimized for the average fidelity of their joint output state with respect to a product of multiple originals. We design 1 to 2 quantum bit cloners using the numerical method for finding completely positive maps approximating a nonphysical one optimally. We discuss the properties of the so-designed cloners.
Quantum error correction (QEC) is an essential element of physical quantum information processing systems. Most QEC efforts focus on extending classical error correction schemes to the quantum regime. The input to a noisy system is embedded in a coded subspace, and error recovery is performed via an operation designed to perfectly correct for a set of errors, presumably a large subset of the physical noise process. In this paper, we examine the choice of recovery operation. Rather than seeking perfect correction on a subset of errors, we seek a recovery operation to maximize the entanglement fidelity for a given input state and noise model. In this way, the recovery operation is optimum for the given encoding and noise process. This optimization is shown to be calculable via a semidefinite program (SDP), a well-established form of convex optimization with efficient algorithms for its solution. The error recovery operation may also be interpreted as a combining operation following a quantum spreading channel, thus providing a quantum analogy to the classical diversity combining operation.
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^c}$, for some constant $c > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
