It is well recognized that excessive ice accumulation at low-temperature conditions can cause significant damage to civil infrastructure. The passive anti-icing surfaces provide a promising solution to suppress ice nucleation and enhance ice removal. However, despite extensive efforts, it remains a challenge to design anti-icing surfaces with low ice adhesion. Using all-atom molecular dynamics (MD) simulations, we show that surfaces with single-walled carbon nanotube array (CNTA) significantly reduce ice adhesion due to the extremely low solid areal fraction. It was found that the CNTA surface exhibits up to a 45% decrease in the ice adhesion strength in comparison with the atomically smooth graphene surface. The details of the ice detachment from the CNTA surface were examined for different water-carbon interaction energies and temperatures of the ice cube. Remarkably, the results of MD simulations demonstrate that the ice detaching strength depends linearly on the ratio of the ice-surface interaction energy and the ice temperature. These results open the possibility for designing novel robust surfaces with low ice adhesion for passive anti-icing applications. (C) 2017 Elsevier B.V. All rights reserved.