Gravity surveys are useful for profiling underground density structures. We propose a hybrid gravity survey method using gravimeters and gravity gradiometers to detect submarine ore deposits, such as massive sulfides buried below the seafloor. This paper describes a gravity gradiometer, which can be implemented in an AUV (Autonomous Underwater Vehicle) for this purpose. We developed a new gravity gradiometer comprising of two vertically separated accelerometers with astatic reference pendulums, whose motions are precisely detected by optical sensors. Two identical pendulums are installed in a forced gimbal to reduce the rotational motion of the underwater vehicle. The Laboratory measurements show that the noise level of the gravity gradiometer is estimated to be 7 E (1 E = 1 × 10−9 /s2), with which typical submarine ore deposits can be detected using the gravity gradiometer implemented in an AUV. The gravity gradiometer is housed in a pressure-proof vessel made of titanium alloy, 500 mm in diameter and 700 mm in height, and the vessel is implemented in an AUV. We plan a sea trial in September, 2012, in Sagami Bay, off the coast of Shizuoka Prefecture in Japan.