In this study, we propose a new representation method for multidimensional color images, called an n-qubit normal arbitrary superposition state (NASS), where n qubits represent the colors and coordinates of 2n pixels (e.g., a three-dimensional color image of 1024×1024×1024 using only 30 qubits). Based on NASS, we present an (n+1)-qubit normal arbitrary superposition state with relative phases (NASSRP) and an (n+2)-qubit normal arbitrary superposition state with three components (NASSTC) for lossless and lossy quantum compression, respectively. We also design three general quantum circuits to generate NASS, NASSRP, and NASSTC states, where we retrieve an image from a quantum system using different projection measurement operators. Finally, we define the quantum compression ratio and analyze lossless and lossy quantum compression algorithms of multidimensional quantum images. For the first time, we implemented the compression of multidimensional color images on a quantum computer. Thus, we address the theoretical and practical aspects of image processing on a quantum computer. © 2014 Elsevier Inc. All rights reserved.