Due to the impressive development of computers in the recent decades, reducing the dimensions of the integrated circuits became necessary. However, limitations in the nature of MOSFET technology has caused the reduction of the dimensions of the semiconductor transistors to face different problems such as effects of short circuits, high leak power consumption, material restrictions and therefore, the desired conditions and circumstances are not met. To overcome these challenges, new nanotechnologies such as Single Electron Transistors, Quantum Cellular Automata and Field-Effect Transistors are considered and studied widely as possible replacement for MOSFET. Quantum Cellular Automata is a set of quantum cells. Each quantum cell contains four quantum-dots and two electrons which are able to be transferred from a quantum-dot in a cell to another quantum-dot in the same cell by tunneling, and thereby, encode binary data based on the position of the electrons. Majority gates are one of the key elements in Quantum Cellular Automata. It is possible to produce any basic logical functions using a majority gate added by an inverter gate. In this work, three new designs for majority gates are designed and introduced. In addition, by using these gates, logical circuits and four innovative Full-Adder cells are designed and implemented. Afterwards, these circuits have been compared with their latest similar samples and have been evaluated and their advantage has been proven. Keywords: Quantum Cellular Automata, Majority Gate, Full Adder, Nanoelectronic