The assignment to $FIXED_STRING is found after the sub call. It hasn't been executed when the sub is called.

(And using a my var without first executing the my statement is undefined behaviour.)

Use

{
    my $FIXED_STRING = 'fixed_string';
    my %persistent;

    sub do_something {
        my $x = $_[0];

        $persistent{$x}{$FIXED_STRING} = rand;

        END {
            for my $k (keys %persistent) {
                print "$k: $persistent{$k}{$FIXED_STRING}\n";
            }
        }
    }
}

for my $q ('a'..'g') {
    do_something($q);
    print "Done computing\n"
}
[download]

or use state.

use feature qw( state );

for my $q ('a'..'g') {
    do_something($q);
    print "Done computing\n"
}

sub do_something {
    my $x = $_[0];

    state $FIXED_STRING = 'fixed_string';
    state $persistent = {};

    $persistent->{$x}{$FIXED_STRING} = rand;

    END {
        for my $k (keys %$persistent) {
            print "$k: $persistent->{$k}{$FIXED_STRING}\n";
        }
    }
}
[download]