my @RE = (qr/[[:lower:]]/, qr/[[:upper:]]/, qr/[0-9]/, qr/[^[:alnum:]]
+/);
sub check {
    local ($_) = @_;
    my $length = length;
    return if $length < 8;
    return if $length < 12 && (! /$RE[0]/ || ! /$RE[1]/ || ! /$RE[2]/ 
+|| ! /$RE[3]/);
    return if $length < 16 && (! /$RE[0]/ || ! /$RE[1]/ || ! /$RE[2]/)
+;
    return if $length < 20 && (! /$RE[0]/ || ! /$RE[1]/);
    return 1
}
[download]

Tested against the tests from Re: Efficient way to verify scalar contents (updated x3) (haukex++).

Update: Or, if you want to abstract away the repeating $RE[...]

use List::Util qw{ any };

my @RE = (qr/[[:lower:]]/, qr/[[:upper:]]/, qr/[0-9]/, qr/[^[:alnum:]]
+/);
sub check {
    my ($password) = @_;
    my $length = length $password;
    return if $length < 8;
    return if $length < 12 && any { $password !~ $RE[$_] } 0 .. 3;
    return if $length < 16 && any { $password !~ $RE[$_] } 0 .. 2;
    return if $length < 20 && any { $password !~ $RE[$_] } 0 .. 1;
    return 1
}
[download]