Topological-Graph Dependencies and Scaling Properties of a Heuristic
Qubit-Assignment Algorithm
- URL: http://arxiv.org/abs/2103.15695v2
- Date: Mon, 14 Mar 2022 14:32:55 GMT
- Title: Topological-Graph Dependencies and Scaling Properties of a Heuristic
Qubit-Assignment Algorithm
- Authors: Matthew Steinberg, Sebastian Feld, Carmen G. Almudever, Michael
Marthaler, Jan-Michael Reiner
- Abstract summary: We present a noise-aware qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on a NISQ device, but does not route qubits during the quantum algorithm's execution)
We find that for small, connected-graph algorithms, our-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms.
- Score: 1.2354542488854734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The qubit-mapping problem aims to assign and route qubits of a quantum
circuit onto a NISQ device in an optimized fashion, with respect to some cost
function. Finding an optimal solution to this problem is known to scale
exponentially in computational complexity; as such, it is imperative to
investigate scalable qubit-mapping solutions for NISQ computation. In this
work, a noise-aware heuristic qubit-assignment algorithm (which assigns initial
placements for qubits in a quantum algorithm to qubits on a NISQ device, but
does not route qubits during the quantum algorithm's execution) is presented
and compared against the optimal \textit{brute-force} solution, as well as a
trivial qubit assignment, with the aim to quantify the performance of our
heuristic qubit-assignment algorithm. We find that for small, connected-graph
algorithms, our heuristic-assignment algorithm faithfully lies in between the
effective upper and lower bounds given by the brute-force and trivial
qubit-assignment algorithms. Additionally, we find that the topological-graph
properties of quantum algorithms with over six qubits play an important role in
our heuristic qubit-assignment algorithm's performance on NISQ devices.
Finally, we investigate the scaling properties of our heuristic algorithm for
quantum processors with up to 100 qubits; here, the algorithm was found to be
scalable for quantum-algorithms which admit path-like graphs. Our findings show
that as the size of the quantum processor in our simulation grows, so do the
benefits from utilizing the heuristic qubit-assignment algorithm, under
particular constraints for our heuristic algorithm. This work thus
characterizes the performance of a heuristic qubit-assignment algorithm with
respect to the topological-graph and scaling properties of a quantum algorithm
which one may wish to run on a given NISQ device.
Related papers
- Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit.
Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets.
Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
arXiv Detail & Related papers (2024-02-22T09:20:54Z) - Evaluating the Practicality of Quantum Optimization Algorithms for
Prototypical Industrial Applications [44.88678858860675]
We investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA) to the solution of a prototypical model in this field.
We compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics.
arXiv Detail & Related papers (2023-11-20T09:09:55Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - A Variational Qubit-Efficient MaxCut Heuristic Algorithm [0.0]
We present a new variational Qubit-Efficient MaxCut (QEMC) algorithm that requires a logarithmic number of qubits with respect to the graph size.
We demonstrate cutting-edge performance for graph instances consisting of up to 32 nodes (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) using noiseless simulations.
arXiv Detail & Related papers (2023-08-20T23:06:18Z) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
We present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits.
Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
arXiv Detail & Related papers (2021-12-21T12:41:31Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
We introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA)
The approximate solution of the max-cut problem can be obtained with probability close to 1.
We compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
arXiv Detail & Related papers (2021-10-15T11:19:48Z) - Optimization and Noise Analysis of the Quantum Algorithm for Solving
One-Dimensional Poisson Equation [17.65730040410185]
We propose an efficient quantum algorithm for solving one-dimensional Poisson equation.
We further develop this algorithm to make it closer to the real application on the noisy intermediate-scale quantum (NISQ) devices.
We analyze the effect of common noise existing in the real quantum devices on our algorithm using the IBM Qiskit toolkit.
arXiv Detail & Related papers (2021-08-27T09:44:41Z) - Qubit-efficient entanglement spectroscopy using qubit resets [0.0]
We develop qubit-efficient quantum algorithms for entanglement spectroscopy on NISQ devices.
Our algorithms use fewer qubits than any previous efficient algorithm while achieving similar performance in the presence of noise.
We also introduce the notion of effective circuit depth as a generalization of standard circuit depth suitable for circuits with qubit resets.
arXiv Detail & Related papers (2020-10-06T23:22:57Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
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.