How to optimize select count(*)..group by?

We have this simple query:

select status, count(*) from customer group by status;

There is already a btree index on status, but, the customer table is huge, and this query must be executed very frequently... an "explain" on this query shows that it is quite costly (and we notice it runs slowly)...

Can someone recommend the best technique to optimize this? We can create new indices, we can re-write this query.. But we'd rather not add new tables or columns if possible (not just to solve this problem).

Thank you,

Bryan