Storage devices may be configured to desirably reduce the time required to perform a physical secure erase operation. The storage device includes a controller that is configured to direct the storage device to receive a physical secure erase command. The storage device can then identify the one or more blocks within the memory array for secure erasure based on the received physical secure erase command. For each block identified for erasure, the storage device further evaluates the block to determine the level type of cells within the block. In response to the cell level type being single-level, a single-cell erase command is issued to perform a single-level cell erase on the block. Conversely, in response to the cell level type being a higher-dimensional cell, a modified single-cell erase command to perform a modified single-level cell erase on the block is issued.