NP-hard problems do not have general polynomial time algorithms. Hybrid quantum-classical algorithms to solve such combinatorial problems have been of great interest in the past few years. Such algorithms are heuristic in nature and aim to obtain an approximate solution. Significant improvements in computational time and/or the ability to treat large problems are some of the principal promises of quantum computing in this regard. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are relatively small. Moreover, the storage of qubits and introduction of entanglement require extreme conditions. An issue with quantum optimization algorithms such as QAOA is that they scale linearly with problem size. Here, we propose a way of modelling which scales logarithmically with problem size – opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. For experimentation we use problems such as Maximum Cut and QUBO formulation of Minimum Partition. These algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on real quantum computers up to a graph size of 256.