Quantum dot cellular automata (QCA) define the nano structure of a basic computer. It is used as an alternative for designing high-speed computer over CMOS technology. The basic logic in QCA is the logic state that does not measure with voltage level; rather it measures the polarity of electrons in cell. The Majority Voter (MV) is first introduced to design the logic circuits, but only using MV, designing complex logic circuit became inefficient. Many proposals had been made for designing QCA logic gate. In this paper we focus on Novel nanostructure, reduced size and efficient design of ??And-Or-Inverter?? (AOI) and also present comparison with previously reported AOI gate. We design New AOI gate using a combination of Nand-Nor-Inverter (NNI) and MV. Simulation result shows almost 54% reductions in size of AOI gate and improving gate delay due to less complexity on compare to early report. We analyze QCA defect on proposed AOI gate and describe its permissible defect tolerance. We also describe NNI with its QCA nano structure.