One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under... Show moreOne of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems. Show less
Gyurik, C.F.S.; Vreumingen, D. van; Dunjko, V. 2023
Quantum phase estimation is a corner-stone in quantum algorithm design, al-lowing for the inference of eigenvalues of exponentially-large sparse matrices. The maximum rate at which these... Show moreQuantum phase estimation is a corner-stone in quantum algorithm design, al-lowing for the inference of eigenvalues of exponentially-large sparse matrices. The maximum rate at which these eigenvalues may be learned, -known as the Heisen-berg limit-, is constrained by bounds on the circuit complexity required to simulate an arbitrary Hamiltonian. Single-control qubit variants of quantum phase estima-tion that do not require coherence between experiments have garnered interest in re-cent years due to lower circuit depth and minimal qubit overhead. In this work we show that these methods can achieve the Heisenberg limit, also when one is un-able to prepare eigenstates of the system. Given a quantum subroutine which pro-vides samples of a 'phase function' g(k) = sigma(j) A(j)e(i Phi)j(k) with unknown eigenphases phi(j )and overlaps A(j )at quantum cost O(k), we show how to estimate the phases {phi(j}) with (root-mean-square) error delta for total quantum cost T = O(delta(-1)). Our scheme com-bines the idea of Heisenberg-limited multi -order quantum phase estimation for a single eigenvalue phase [1, 2] with subroutines with so-called dense quantum phase estimation which uses classical processing via time-series analysis for the QEEP problem [3] or the matrix pencil method. For our algorithm which adaptively fixes the choice for k in g(k) we prove Heisenberg -limited scaling when we use the time-series/QEEP subroutine. We present numerical evidence that using the matrix pencil technique the algorithm can achieve Heisenberg-limited scaling as well. Show less
Quantum machine learning (QML) has been identified as one of the key fields that could reap advantages from near-term quantum devices, next to optimization and quantum chemistry. Research in this... Show moreQuantum machine learning (QML) has been identified as one of the key fields that could reap advantages from near-term quantum devices, next to optimization and quantum chemistry. Research in this area has focused primarily on variational quantum algorithms (VQAs), and several proposals to enhance supervised, unsupervised and reinforcement learning (RL) algorithms with VQAs have been put forward. Out of the three, RL is the least studied and it is still an open question whether VQAs can be competitive with state-of-the-art classical algorithms based on neural networks (NNs) even on simple benchmark tasks. In this work, we introduce a training method for parametrized quantum circuits (PQCs) that can be used to solve RL tasks for discrete and continuous state spaces based on the deep Q-learning algorithm. We investigate which architectural choices for quantum Q-learning agents are most important for successfully solving certain types of environments by performing ablation studies for a number of different data encoding and readout strategies. We provide insight into why the performance of a VQA-based Q-learning algorithm crucially depends on the observables of the quantum model and show how to choose suitable observables based on the learning task at hand. To compare our model against the classical DQN algorithm, we perform an extensive hyperparameter search of PQCs and NNs with varying numbers of parameters. We confirm that similar to results in classical literature, the architectural choices and hyperparameters contribute more to the agents' success in a RL setting than the number of parameters used in the model. Finally, we show when recent separation results between classical and quantum agents for policy gradient RL can be extended to inferring optimal Q-values in restricted families of environments. This work paves the way towards new ideas on how a quantum advantage may be obtained for real-world problems in the future. Show less
Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of... Show moreQuantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machitie learning. A fundamental parameter governing the efficiency of QLS solvers is is, the condition number of the coefficient matrix A, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in kappa [1]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as root kappa, a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in kappa also when A is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in kappa: the first is based on efficiently implementing a matrix-block-encoding of A(-1), the second constructs a decomposition of the form A=LL dagger to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems. Show less
yalouz, S.; Senjean, B.; Miatto, F.; Dunjko, V. 2021
Variational quantum algorithms (VQA) are considered as some of the most promising methods to determine the properties of complex strongly correlated quantum many-body systems, especially from the... Show moreVariational quantum algorithms (VQA) are considered as some of the most promising methods to determine the properties of complex strongly correlated quantum many-body systems, especially from the perspective of devices available in the near term. In this context, the development of efficient quantum circuit ansatze to encode a many-body wavefunction is one of the keys for the success of a VQA. Great efforts have been invested to study the potential of current quantum devices to encode the eigenstates of fermionic systems, but little is known about the encoding of bosonic systems. In this work, we investigate the encoding of the ground state of the (simple but rich) attractive Bose-Hubbard model using a Continuous-Variable (CV) photonic-based quantum circuit. We introduce two different ansatz architectures and demonstrate that the proposed continuous variable quantum circuits can accurately encode (with a fidelity higher than 99%) the strongly correlated many-boson wavefunction with just a few layers, in all many-body regimes and for different number of bosons and initial states. Beyond the study of the suitability of the ansatz to approximate the ground states of many-boson systems, we also perform initial evaluations of the use of the ansatz in a variational quantum eigensolver algorithm to find it through energy minimization. To this end we also introduce a scheme to measure the Hamiltonian energy in an experimental system , and study the effect of sampling noise. Show less
Marconi, C.; Aloy, A.; Tura Brugués, J.; Sanpera, A. 2021
Entanglement in symmetric quantum states and the theory of copositive matrices are intimately related concepts. For the simplest symmetric states, i.e., the diagonal symmetric (DS) states, it has... Show moreEntanglement in symmetric quantum states and the theory of copositive matrices are intimately related concepts. For the simplest symmetric states, i.e., the diagonal symmetric (DS) states, it has been shown that there exists a correspondence between exceptional (non-exceptional) copositive matrices and non-decomposable (decomposable) entanglement witnesses (EWs). Here we show that EWs of symmetric, but not DS, states can also be constructed from extended copositive matrices, providing new examples of bound entangled symmetric states, together with their corresponding EWs, in arbitrary odd dimension. Show less
