  Quantum computers must meet extremely stringent qualitative and quantitative
requirements on their qubits in order to solve real-life problems. Quantum
circuit fragmentation techniques divide a large quantum circuit into a number
of sub-circuits that can be executed on the smaller noisy quantum hardware
available. However, the process of quantum circuit fragmentation involves
finding an ideal cut that has exponential time complexity, and also classical
post-processing required to reconstruct the output. In this paper, we represent
a quantum circuit using a weighted graph and propose a novel classical graph
partitioning algorithm for selecting an efficient fragmentation that reduces
the entanglement between the sub-circuits along with balancing the estimated
error in each sub-circuit. We also demonstrate a comparative study over
different classical and quantum approaches of graph partitioning for finding
such a cut. We present {\it FragQC}, a software tool that cuts a quantum
circuit into sub-circuits when its error probability exceeds a certain
threshold. With this proposed approach, we achieve an increase of fidelity by
14.83\% compared to direct execution without cutting the circuit, and 8.45\%
over the state-of-the-art ILP-based method, for the benchmark circuits.
