# Quantum Computational Phase Transition in Combinatorial Problems

@inproceedings{Zhang2021QuantumCP, title={Quantum Computational Phase Transition in Combinatorial Problems}, author={Bingzhi Zhang and Akira Sone and Quntao Zhuang}, year={2021} }

Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. To search for such a quantum advantage in solving any problem, it is crucial to first understand the difference between problem instances’ empirical hardness for QAOA and classical algorithms. We identify a computational phase transition of QAOA when solving hard problems such as 3-SAT—the performance is worst at the well-known SAT-UNSAT phase transition, where the hardest… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 51 REFERENCES

Reachability Deficits in Quantum Approximate Optimization

- Computer Science, Medicine
- Physical review letters
- 2020

It is reported that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio-this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Expand

Some optimal inapproximability results

- Computer Science, Mathematics
- JACM
- 2001

We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations… Expand

"J."

- 1890

however (for it was the literal soul of the life of the Redeemer, John xv. io), is the peculiar token of fellowship with the Redeemer. That love to God (what is meant here is not God’s love to men)… Expand

Cost function dependent barren plateaus in shallow parametrized quantum circuits

- Medicine
- Nature communications
- 2021

This work rigorously proves two results, assuming V(θ) is an alternating layered ansatz composed of blocks forming local 2-designs, that establish a connection between locality and trainability. Expand

QuTiP: An open-source Python framework for the dynamics of open quantum systems

- Physics, Computer Science
- Comput. Phys. Commun.
- 2012

An object-oriented open-source framework for solving the dynamics of open quantum systems written in Python that is particularly well suited to the fields of quantum optics, superconducting circuit devices, nanomechanics, and trapped ions, while also being ideal for use in classroom instruction. Expand

Approximation Algorithms for the Weighted Independent Set Problem

- Mathematics, Computer Science
- WG
- 2005

Algorithms for the weighted independent set problem in terms of weighted measures, namely “weighted” average degree and “ weights of inductiveness,” are analyzed and results are analyzed. Expand

A note on greedy algorithms for the maximum weighted independent set problem

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2003

Three simple and natural greedy algorithms for the maximum weighted independent set problem are considered and it is shown that two of them output an independent set of weight at least Σv∈V(G) W(v)/[d(v) + 1]. Expand

Diagnosing barren plateaus with tools from quantum optimal control

- Physics
- 2021

Martín Larocca,1, 2 Piotr Czarnik,2 Kunal Sharma,3, 2 Gopikrishnan Muraleedharan,2 Patrick J. Coles,2 and M. Cerezo2, 4 Departamento de Física “J. J. Giambiagi” and IFIBA, FCEyN, Universidad de… Expand

Noise-induced barren plateaus in variational quantum algorithms

- Physics, Computer Science
- Nature communications
- 2021

This work rigorously proves a serious limitation for noisy VQAs, in that the noise causes the training landscape to have a barren plateau (i.e., vanishing gradient), and implements numerical heuristics that confirm the NIBP phenomenon for a realistic hardware noise model. Expand

Theory of overparametrization in quantum neural networks

- Computer Science, Physics
- ArXiv
- 2021

This paper presents a meta-analyses of the LaSalle–Cerezo–Larocca–Bouchut–Seiden–Stein cellular automaton, a model derived from the model developed by J. J. Giambiagi in 2007, which states that the model derived in this paper can be modified for flows on rugous topographies varying around an inclined plane. Expand