Search

Understanding the physics of strongly correlated materials is one of the grand challenge problems for physics today. A large class of scientifically interesting materials, from high-$T_c$ superconductors to spin liquids, involve medium to strong correlations, and building a holistic understanding of these materials is critical. Doing so is hindered by the competition between the kinetic energy and Coulomb repulsion, which renders both analytic and numerical methods unsatisfactory for describing interacting materials. Fault-tolerant quantum computers have been proposed as a path forward to overcome these difficulties, but this potential capability has not yet been fully assessed. Here, using the multi-orbital Fermi-Hubbard model as a representative model and a source of scalable problem specifications, we estimate the resource costs needed to use fault-tolerant quantum computers for obtaining experimentally relevant quantities such as correlation function estimation. We find that advances in quantum algorithms and hardware will be needed in order to reduce quantum resources and feasibly address utility-scale problem instances.

The development of fault-tolerant quantum computers (FTQCs) is gaining increased attention within the quantum computing community. Like their digital counterparts, FTQCs, equipped with error correction and large qubit numbers, promise to solve some of humanity's grand challenges. Estimates of the resource requirements for future FTQC systems are essential to making design choices and prioritizing R&D efforts to develop critical technologies. Here, we present a resource estimation framework and software tool that estimates the physical resources required to execute specific quantum algorithms, compiled into their graph-state form, and laid out onto a modular superconducting hardware architecture. This tool can predict the size, power consumption, and execution time of these algorithms at as they approach utility-scale according to explicit assumptions about the system's physical layout, thermal load, and modular connectivity. We use this tool to study the total resources on a proposed modular architecture and the impact of tradeoffs between and inter-module connectivity, latency and resource requirements.

Achieving high-quality solutions faster than classical solvers on computationally hard problems is a challenge for quantum optimization to deliver utility. Using a superconducting quantum computer, we experimentally investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite programming approaches for solving the maximum-cut problem on 3-regular graphs up to several thousand variables. We leverage the structure of the input problems to address sizes beyond what current quantum machines can naively handle. We attain an average approximation ratio of 99% over a random ensemble of thousands of problem instances. We benchmark the quantum solver against similarly high-performing classical heuristics, including the Gurobi optimizer, simulated annealing, and the Burer-Monteiro algorithm. A run-time analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others on a projected 100-qubit quantum computer. We explore multiple leads to close the gap and discuss prospects for a practical quantum speedup., Comment: 35 pages, 26 figures

We develop a hardware-efficient ansatz for variational optimization, derived from existing ansatze in the literature, that parametrizes subsets of all interactions in the Cost Hamiltonian in each layer. We treat gate orderings as a variational parameter and observe that doing so can provide significant performance boosts in experiments. We carried out experimental runs of a compilation-optimized implementation of fully-connected Sherrington-Kirkpatrick Hamiltonians on a 50-qubit linear-chain subsystem of Rigetti Aspen-M-3 transmon processor. Our results indicate that, for the best circuit designs tested, the average performance at optimized angles and gate orderings increases with circuit depth (using more parameters), despite the presence of a high level of noise. We report performance significantly better than using a random guess oracle for circuits involving up to approx 5000 two-qubit and approx 5000 one-qubit native gates. We additionally discuss various takeaways of our results toward more effective utilization of current and future quantum processors for optimization., Comment: v2: extended experimental results, updated references, fixed typos; v3: improved main narration, added new experimental data and analysis, updated references, fixed typos; v4: slightly improved narration, updated references 15+8 pages; 3+5 figures

Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics., Comment: 9 pages, 5 figures (+ 12 pages, 11 figures)

Many quantum algorithms seek to output a specific bitstring solving the problem of interest--or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial $N$-qubit product state $\vert 0\rangle^{\otimes N}$ and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic Max-Cut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same Max-Cut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states., Comment: 12 pages, 7 figures

Trading fidelity for scale enables approximate classical simulators such as matrix product states (MPS) to run quantum circuits beyond exact methods. A control parameter, the so-called bond dimension $\chi$ for MPS, governs the allocated computational resources and the output fidelity. Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function it seeks to minimize and find that it follows a scaling law $F\bigl(\ln\chi\bigr/N\bigr)$ with $N$ the number of qubits. With $\ln\chi$ amounting to the entanglement that an MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit. Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup. For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function. Moreover, we relate the global fidelity to that of individual operations and establish its relationship with $\chi$ and $N$. We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity., Comment: 13 pages, 11 figures

Developing quantum computers for real-world applications requires understanding theoretical sources of quantum advantage and applying those insights to design more powerful machines. Toward that end, we introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis (CCPHASE$(\theta)$). We estimate the process fidelity for this scheme via Cycle Benchmarking of $\mathcal{F}=87.1\pm0.8\%$, higher than reference two-qubit gate decompositions. CCPHASE$(\theta)$ is anticipated to have broad experimental implications, and we report a blueprint demonstration for solving a class of binary constraint satisfaction problems whose construction is consistent with a path to quantum advantage., Comment: 12 pages, 10 figures

In order to assess whether quantum resources can provide an advantage over classical computation, it is necessary to characterize and benchmark the non-classical properties of quantum algorithms in a practical manner. In this paper, we show that using measurements in no more than 3 out of the possible $3^N$ bases, one can not only reconstruct the single-qubit reduced density matrices and measure the ability to create coherent superpositions, but also possibly verify entanglement across all $N$ qubits participating in the algorithm. We introduce a family of generalized Bell-type observables for which we establish an upper bound to the expectation values in fully separable states by proving a generalization of the Cauchy-Schwarz inequality, which may serve of independent interest. We demonstrate that a subset of such observables can serve as entanglement witnesses for QAOA-MaxCut states, and further argue that they are especially well tailored for this purpose by defining and computing an entanglement potency metric on witnesses. A subset of these observables also certify, in a weaker sense, the entanglement in GHZ states, which share the $\mathbb{Z}_2$ symmetry of QAOA-MaxCut. The construction of such witnesses follows directly from the cost Hamiltonian to be optimized, and not through the standard technique of using the projector of the state being certified. It may thus provide insights to construct similar witnesses for other variational algorithms prevalent in the NISQ era. We demonstrate our ideas with proof-of-concept experiments on the Rigetti Aspen-9 chip for ansatze containing up to 24 qubits.

This paper establishes the tractability of finding the optimal Nash equilibrium, as well as the optimal social solution, to a discrete congestion game using a gate-model quantum computer. The game is of the type originally posited by Rosenthal in the 1970's. To find the optimal Nash equilibrium, we formulate an optimization problem encoding based on potential functions and path selection constraints, and solve it using the Quantum Alternating Operator Ansatz. We compare this formulation to its predecessor, the Quantum Approximate Optimization Algorithm. We implement our solution on an idealized simulator of a gate-model quantum computer, and demonstrate tractability on a small two-player game. This work provides the basis for future endeavors to apply quantum approximate optimization to quantum machine learning problems, such as the efficient training of generative adversarial networks using potential functions., Comment: 11 pages, pre-print. arXiv admin note: text overlap with arXiv:1911.05296

This paper investigates the experimental performance of a discrete portfolio optimization problem relevant to the financial services industry on the gate-model of quantum computing. We implement and evaluate a portfolio rebalancing use case on an idealized simulator of a gate-model quantum computer. The characteristics of this exemplar application include trading in discrete lots, non-linear trading costs, and the investment constraint. We design a novel problem encoding and hard constraint mixers for the Quantum Alternating Operator Ansatz, and compare to its predecessor the Quantum Approximate Optimization Algorithm. Experimental analysis demonstrates the potential tractability of this application on Noisy Intermediate-Scale Quantum (NISQ) hardware, identifying portfolios within 5% of the optimal adjusted returns and with the optimal risk for a small eight-stock portfolio., Comment: 9 pages, pre-print