Quantum mean states are nicer than you think: fast algorithms to compute
states maximizing average fidelity
- URL: http://arxiv.org/abs/2206.08183v1
- Date: Thu, 16 Jun 2022 13:52:01 GMT
- Title: Quantum mean states are nicer than you think: fast algorithms to compute
states maximizing average fidelity
- Authors: A. Afham, Richard Kueng, Chris Ferrie
- Abstract summary: We resolve the open problem of maximizing average fidelity over arbitrary finite ensembles of quantum states.
We first construct a semidefinite program whose optimal value is the maximum average fidelity and then derive fixed-point algorithms that converge to the optimal state.
We also derive expressions for near-optimal states that are easier to compute and upper and lower bounds for maximum average fidelity that are exact when all the states in the ensemble commute.
- Score: 1.9336815376402714
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Fidelity is arguably the most popular figure of merit in quantum sciences.
However, many of its properties are still unknown. In this work, we resolve the
open problem of maximizing average fidelity over arbitrary finite ensembles of
quantum states and derive new upper bounds. We first construct a semidefinite
program whose optimal value is the maximum average fidelity and then derive
fixed-point algorithms that converge to the optimal state. The fixed-point
algorithms outperform the semidefinite program in terms of numerical runtime.
We also derive expressions for near-optimal states that are easier to compute
and upper and lower bounds for maximum average fidelity that are exact when all
the states in the ensemble commute. Finally, we discuss how our results solve
some open problems in Bayesian quantum tomography.
Related papers
- Leveraging modular values in quantum algorithms: the Deutsch-Jozsa [0.0]
We present a novel approach to quantum algorithms, by taking advantage of modular values.
We focus on the problem of ascertaining whether a given function acting on a set of binary values is constant.
The proposed method, relying on the use of modular values, provides a high number of degrees of freedom for optimizing the new algorithm.
arXiv Detail & Related papers (2024-06-10T21:17:07Z) - An improved Quantum Max Cut approximation via matching [0.10878040851638002]
A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian.
We present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.584 given a generic input.
arXiv Detail & Related papers (2024-01-08T00:36:32Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
A feature of constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard.
For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class.
We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_mathrmunsat-N_mathrmsat$, spectrally filtered quantum optimization will return states with $E leq q_m.
arXiv Detail & Related papers (2023-12-11T04:15:55Z) - Maximum expectation of observables with restricted purity states [2.7624021966289605]
Assessment of practical quantum information processing (QIP) remains partial without understanding limits imposed by noise.
We fulfill the need for estimates on performing noisy quantum state preparation, verification, and observation.
We also give a simple but fundamental insight, noisy systems always give higher ground-state energy than their noiseless counterparts.
arXiv Detail & Related papers (2023-11-13T19:02:35Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
arXiv Detail & Related papers (2020-12-11T08:28:51Z) - Improving the Quantum Approximate Optimization Algorithm with
postselection [0.0]
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers.
We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs.
We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
arXiv Detail & Related papers (2020-11-10T22:17:50Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.