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 ma
ke 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.
Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely, with minimal assumptions about the underlying quantum system. It is based on the observation that some extremal points in the set of qu
antum correlations can only be achieved, up to isometries, with specific states and measurements. Here, we present a new approach for quantum self-testing in Bell non-locality scenarios, motivated by the following observation: the quantum maximum of a given Bell inequality is, in general, difficult to characterize. However, it is strictly contained in an easy-to-characterize set: the emph{theta body} of a vertex-weighted induced subgraph $(G,w)$ of the graph in which vertices represent the events and edges join mutually exclusive events. This implies that, for the cases where the quantum maximum and the maximum within the theta body (known as the Lovasz theta number) of $(G,w)$ coincide, self-testing can be demonstrated by just proving self-testability with the theta body of $G$. This graph-theoretic framework allows us to (i) recover the self-testability of several quantum correlations that are known to permit self-testing (like those violating the Clauser-Horne-Shimony-Holt (CHSH) and three-party Mermin Bell inequalities for projective measurements of arbitrary rank, and chained Bell inequalities for rank-one projective measurements), (ii) prove the self-testability of quantum correlations that were not known using existing self-testing techniques (e.g., those violating the Abner Shimony Bell inequality for rank-one projective measurements). Additionally, the analysis of the chained Bell inequalities gives us a closed-form expression of the Lovasz theta number for a family of well-studied graphs known as the Mobius ladders, which might be of independent interest in the community of discrete mathematics.
To harness the potential of noisy intermediate-scale quantum devices, it is paramount to find the best type of circuits to run hybrid quantum-classical algorithms. Key candidates are parametrized quantum circuits that can be effectively implemented o
n current devices. Here, we evaluate the capacity and trainability of these circuits using the geometric structure of the parameter space via the effective quantum dimension, which reveals the expressive power of circuits in general as well as of particular initialization strategies. We assess the expressive power of various popular circuit types and find striking differences depending on the type of entangling gates used. Particular circuits are characterized by scaling laws in their expressiveness. We identify a transition in the quantum geometry of the parameter space, which leads to a decay of the quantum natural gradient for deep circuits. For shallow circuits, the quantum natural gradient can be orders of magnitude larger in value compared to the regular gradient; however, both of them can suffer from vanishing gradients. By tuning a fixed set of circuit parameters to randomized ones, we find a region where the circuit is expressive, but does not suffer from barren plateaus, hinting at a good way to initialize circuits. We show an algorithm that prunes redundant parameters of a circuit without affecting its effective dimension. Our results enhance the understanding of parametrized quantum circuits and can be immediately applied to improve variational quantum algorithms.
We provide a bucket of noisy intermediate-scale quantum era algorithms for simulating the dynamics of open quantum systems, generalized time evolution, non-linear differential equations and Gibbs state preparation. Our algorithms do not require any c
lassical-quantum feedback loop, bypass the barren plateau problem and do not necessitate any complicated measurements such as the Hadamard test. To simplify and bolster our algorithms, we introduce the notion of the hybrid density matrix. The aforementioned concept enables us to disentangle the different steps of our algorithm and facilitate delegation of the classically demanding tasks to the quantum computer. Our algorithms proceed in three disjoint steps. The first step entails the selection of the Ansatz. The second step corresponds to the measuring overlap matrices on a quantum computer. The final step involves classical post-processing based on the data from the second step. Due to the absence of the quantum-classical feedback loop, the quantum part of our algorithms can be parallelized easily. Our algorithms have potential applications in solving the Navier-Stokes equation, plasma hydrodynamics, quantum Boltzmann training, quantum signal processing and linear systems, among many. The entire framework is compatible with the current experimental faculty and hence can be implemented immediately.
Quantum simulation can help us study poorly understood topics such as high-temperature superconductivity and drug design. However, existing quantum simulation algorithms for current quantum computers often have drawbacks that impede their application
. Here, we provide a novel hybrid quantum-classical algorithm for simulating the dynamics of quantum systems. Our approach takes the Ansatz wavefunction as a linear combination of quantum states. The quantum states are fixed, and the combination parameters are variationally adjusted. Unlike existing variational quantum simulation algorithms, our algorithm does not require any classical-quantum feedback loop and by construction bypasses the barren plateau problem. Moreover, our algorithm does not require any complicated measurements such as the Hadamard test. The entire framework is compatible with existing experimental capabilities and thus can be implemented immediately.
Quantum thermodynamics has emerged as a separate sub-discipline, revising the concepts and laws of thermodynamics, at the quantum scale. In particular, there has been a disruptive shift in the way thermometry, and thermometers are perceived and desig
ned. Currently, we face two major challenges in quantum thermometry. First, all of the existing optimally precise temperature probes are local, meaning their operation is optimal only for a narrow range of temperatures. Second, aforesaid optimal local probes mandate complex energy spectrum with immense degeneracy, rendering them impractical. Here, we address these challenges by formalizing the notion of global thermometry leading to the development of optimal temperature sensors over a wide range of temperatures. We observe the emergence of different phases for such optimal probes as the temperature interval is increased. In addition, we show how the best approximation of optimal global probes can be realized in spin chains, implementable in ion traps and quantum dots.
The task of estimating the ground state of Hamiltonians is an important problem in physics with numerous applications ranging from solid-state physics to combinatorial optimization. We provide a hybrid quantum-classical algorithm for approximating th
e ground state of a Hamiltonian that builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers. Our algorithm systematically constructs the Ansatz using any given choice of the initial state and the unitaries describing the Hamiltonian. The only task of the quantum computer is to measure overlaps and no feedback loops are required. The measurements can be performed efficiently on current quantum hardware without requiring any complicated measurements such as the Hadamard test. Finally, a classical computer solves a well characterized quadratically constrained optimization program. Our algorithm can reuse previous measurements to calculate the ground state of a wide range of Hamiltonians without requiring additional quantum resources. Further, we demonstrate our algorithm for solving problems consisting of thousands of qubits. The algorithm works for almost every random choice of the initial state and circumvents the barren plateau problem.
A fundamental problem in quantum computation and quantum information is finding the minimum quantum dimension needed for a task. For tasks involving state preparation and measurements, this problem can be addressed using only the input-output correla
tions. This has been applied to Bell, prepare-and-measure, and Kochen-Specker contextuality scenarios. Here, we introduce a novel approach to quantum dimension witnessing for scenarios with one preparation and several measurements, which uses the graphs of mutual exclusivity between sets of measurement events. We present the concepts and tools needed for graph-theoretic quantum dimension witnessing and illustrate their use by identifying novel quantum dimension witnesses, including a family that can certify arbitrarily high quantum dimensions with few events.
The onset of the era of fully-programmable error-corrected quantum computers will be marked by major breakthroughs in all areas of science and engineering. These devices promise to have significant technological and societal impact, notable examples
being the analysis of big data through better machine learning algorithms and the design of new materials. Nevertheless, the capacity of quantum computers to faithfully implement quantum algorithms relies crucially on their ability to prepare specific high-dimensional and high-purity quantum states, together with suitable quantum measurements. Thus, the unambiguous certification of these requirements without assumptions on the inner workings of the quantum computer is critical to the development of trusted quantum processors. One of the most important approaches for benchmarking quantum devices is through the mechanism of self-testing that requires a pair of entangled non-communicating quantum devices. Nevertheless, although computation typically happens in a localized fashion, no local self-testing scheme is known to benchmark high dimensional states and measurements. Here, we show that the quantum self-testing paradigm can be employed to an individual quantum computer that is modelled as a programmable black box by introducing a noise-tolerant certification scheme. We substantiate the applicability of our scheme by providing a family of outcome statistics whose observation certifies that the computer is producing specific high-dimensional quantum states and implementing specific measurements.
Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources a
re not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax = b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300} times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.
