Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer
141
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We demonstrate that a quantum annealer can be used to solve the NP-complete problem of graph partitioning into subgraphs containing Hamiltonian cycles of constrained length. We present a method to find a partition of a given directed graph into Hamiltonian subgraphs with three or more vertices, called vertex 3-cycle cover. We formulate the problem as a quadratic unconstrained binary optimisation and run it on a D-Wave Advantage quantum annealer. We test our method on synthetic graphs constructed by adding a number of random edges to a set of disjoint cycles. We show that the probability of solution is independent of the cycle length, and a solution is found for graphs up to 4000 vertices and 5200 edges, close to the number of physical working qubits available on the quantum annealer.
rate research
Read More
Current quantum computer designs will not scale. To scale beyond small prototypes, quantum architectures will likely adopt a modular approach with clusters of tightly connected quantum bits and sparser connections between clusters. We exploit this clustering and the statically-known control flow of quantum programs to create tractable partitioning heuristics which map quantum circuits to modular physical machines one time slice at a time. Specifically, we create optimized mappings for each time slice, accounting for the cost to move data from the previous time slice and using a tunable lookahead scheme to reduce the cost to move to future time slices. We compare our approach to a traditional statically-mapped, owner-computes model. Our results show strict improvement over the static mapping baseline. We reduce the non-local communication overhead by 89.8% in the best case and by 60.9% on average. Our techniques, unlike many exact solver methods, are computationally tractable.
The ability to simulate a fermionic system on a quantum computer is expected to revolutionize chemical engineering, materials design, nuclear physics, to name a few. Thus, optimizing the simulation circuits is of significance in harnessing the power of quantum computers. Here, we address this problem in two aspects. In the fault-tolerant regime, we optimize the $rzgate$ and $tgate$ gate counts along with the ancilla qubit counts required, assuming the use of a product-formula algorithm for implementation. We obtain a savings ratio of two in the gate counts and a savings ratio of eleven in the number of ancilla qubits required over the state of the art. In the pre-fault tolerant regime, we optimize the two-qubit gate counts, assuming the use of the variational quantum eigensolver (VQE) approach. Specific to the latter, we present a framework that enables bootstrapping the VQE progression towards the convergence of the ground-state energy of the fermionic system. This framework, based on perturbation theory, is capable of improving the energy estimate at each cycle of the VQE progression, by about a factor of three closer to the known ground-state energy compared to the standard VQE approach in the test-bed, classically-accessible system of the water molecule. The improved energy estimate in turn results in a commensurate level of savings of quantum resources, such as the number of qubits and quantum gates, required to be within a pre-specified tolerance from the known ground-state energy. We also explore a suite of generalized transformations of fermion to qubit operators and show that resource-requirement savings of up to more than $20%$, in small instances, is possible.
A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $Gamma=(V,E)$, ($psi_{k}^{gd}(Gamma)$) $psi_k^{d}(Gamma)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $psi_k^{d}(Gamma)$ and $psi_{k}^{gd}(Gamma)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Gamma_1times Gamma_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $Gamma_i$ into (global) defensive $k_i$-alliances, $iin {1,2}$.
Experimental demonstrations of quantum annealing with native implementation of Boolean logic Hamiltonians are reported. As a superconducting integrated circuit, a problem Hamiltonian whose set of ground states is consistent with a given truth table is implemented for quantum annealing with no redundant qubits. As examples of the truth table, NAND and NOR are successfully fabricated as an identical circuit. Similarly, a native implementation of a multiplier comprising six superconducting flux qubits is also demonstrated. These native implementations of Hamiltonians consistent with Boolean logic provide an efficient and scalable way of applying annealing computation to so-called circuit satisfiability problems that aim to find a set of inputs consistent with a given output over any Boolean logic functions, especially those like factorization through a multiplier Hamiltonian. A proof-of-concept demonstration of a hybrid computing architecture for domain-specific quantum computing is described.
Quantum computers are ideal for solving chemistry problems due to their polynomial scaling with system size in contrast to classical computers which scale exponentially. Until now molecular energy calculations using quantum computing hardware have been limited to quantum simulators. In this paper, a new methodology is presented to calculate the vibrational spectrum of a molecule on a quantum annealer. The key idea of the method is a mapping of the ground state variational problem onto an Ising or quadratic unconstrained binary optimization (QUBO) problem by expressing the expansion coefficients using spins or qubits. The algorithm is general and represents a new revolutionary approach for solving the real symmetric eigenvalue problem on a quantum annealer. The method is applied to two chemically important molecules: O$_2$ (oxygen) and O$_3$ (ozone). The lowest two vibrational states of these molecules are computed using both a hardware quantum annealer and a software based classical annealer.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
