A bounded-error quantum polynomial-time algorithm for two graph bisection problems

DOI10.1007/S11128-015-1069-YMaRDI QIDQ747789zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ahmed Younes

Publication date 19 October 2015

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06284

zbMATH Keywords

quantum algorithmNP-hardamplitude amplificationBQPgraph bisectionMAX-bisectionMIN-bisection

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Graph designs and isomorphic decomposition (05C51)

Abstract: The aim of the paper is to propose a bounded-error quantum polynomial time (BQP) algorithm for the max-bisection and the min-bisection problems. The max-bisection and the min-bisection problems are fundamental NP-hard problems. Given a graph with even number of vertices, the aim of the max-bisection problem is to divide the vertices into two subsets of the same size to maximize the number of edges between the two subsets, while the aim of the min-bisection problem is to minimize the number of edges between the two subsets. The proposed algorithm runs in $O(m^2)$ for a graph with $m$ edges and in the worst case runs in $O(n^4)$ for a dense graph with $n$ vertices. The proposed algorithm targets a general graph by representing both problems as Boolean constraint satisfaction problems where the set of satisfied constraints are simultaneously maximized/minimized using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of $1-epsilon$ for small $epsilon>0$ using a polynomial space resources.

Recommendations

• Approximating the minimum bisection size (extended abstract)
• Quantum property testing for bounded-degree graphs
• An exact combinatorial algorithm for minimum graph bisection
• A quantum-walk-inspired adiabatic algorithm for solving graph isomorphism problems
• Quantum algorithms for matching problems

Cites work

• scientific article; zbMATH DE number 48688 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• A framework for solving VLSI graph layout problems
• Algorithms and Computation
• An Automatic Method of Solving Discrete Programming Problems
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• An exact algorithm for graph partitioning
• An exact combinatorial algorithm for minimum graph bisection
• Applications of a Planar Separator Theorem
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Distributed Evolutionary Graph Partitioning
• Enhanced quantum searching via entanglement and partial diffusion
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Min-cut clustering
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Some simplified NP-complete graph problems
• The RPR2 rounding technique for semidefinite programs

Cited in

(3)

• Reading a single qubit system using weak measurement with variable strength
• A dynamic programming approach for distributing quantum circuits by bipartite graphs
• Quantum algorithm for quantum state discrimination via partial negation and weak measurement

Describes a project that uses

Uses Software

• KaHIP
• Pregel
• DibaP
• KaFFPa

This page was built for publication: A bounded-error quantum polynomial-time algorithm for two graph bisection problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747789)