Source author record

Mehdi Soleimanifar

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

quant-ph Data Structures and Algorithms Computational Complexity cond-mat.stat-mech Information Theory math.IT

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Testing matrix product states

Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. Here, we study the problem of testing whether an unknown state $|ψ\rangle$ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state $|ψ_{1,...,n}\rangle$ comprised of $n$ qudits is said to be an MPS of bond dimension $r$ if the reduced density matrix $ψ_{1,...,k}$ has rank $r$ for each $k \in \{1,...,n\}$ . When $r=1$ , this corresponds to the set of product states. For larger values of $r$ , this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. In the property testing model, one is given $m$ identical copies of $|ψ\rangle$ , and the goal is to determine whether $|ψ\rangle$ is an MPS of bond dimension $r$ or whether $|ψ\rangle$ is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro (FOCS 2010), and a key ingredient in their proof that $\mathsf{QMA(2)}=\mathsf{QMA}(k)$ for $k \geq 2$ . We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems of Harrow and Montanaro (FOCS 2010) and Montanaro and de Wolf (2016). For the case of $r\geq 2$ , we give an efficient algorithm for testing whether $|ψ\rangle$ is an MPS of bond dimension $r$ using $m = O(n r^2)$ copies, independent of the dimensions of the qudits, and we show that $Ω(n^{1/2})$ copies are necessary for this task. This lower bound shows that a dependence on the number of qudits $n$ is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.

preprint2021arXiv

Improved approximation algorithms for bounded-degree local Hamiltonians

We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an $n$ -qubit product state $|v\rangle$ with mean energy $e_0=\langle v|H|v\rangle$ and variance $\mathrm{Var}=\langle v|(H-e_0)^2|v\rangle$ , and outputs a state with an energy that is lower than $e_0$ by an amount proportional to $\mathrm{Var}^2/n$ . In a typical case, we have $\mathrm{Var}=Ω(n)$ and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to $k$ -local Hamiltonians and entangled initial states.

preprint2019arXiv

Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

In this paper, we present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least log(n) decays exponentially. We can improve the factor of log(n) to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.

preprint2016arXiv

No-iteration of unknown quantum gates

We propose a new no-go theorem by proving the impossibility of constructing a deterministic quantum circuit that iterates a unitary oracle by calling it only once. Different schemes are provided to bypass this result and to approximately realize the iteration. The optimal scheme is also studied. An interesting observation is that for large number of iterations, a trivial strategy like using the identity channel has the optimal performance, and preprocessing, postprocessing, or using resources like entanglement does not help at all. Intriguingly, the number of iterations, when being large enough, does not affect the performance of the proposed schemes.

preprint2014arXiv

Adaptive Molecule Transmission Rate for Diffusion Based Molecular Communication

In this paper, a simple memory limited transmitter for molecular communication is proposed, in which information is encoded in the diffusion rate of the molecules. Taking advantage of memory, the proposed transmitter reduces the ISI problem by properly adjusting its diffusion rate. The error probability of the proposed scheme is derived and the result is compared with the lower bound on error probability of the optimum transmitter. It is shown that the performance of introduced transmitter is near optimal (under certain simplifications). Simplicity is the key feature of the presented communication system: the transmitter follows a simple rule, the receiver is a simple threshold decoder and only one type of molecule is used to convey the information.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.