Adding few points to @crmprogdev answer. It is not possible to use dependency in multiselect picklist. But you can try something similar in custom VF page.
Just create a Map<String, set<string>>
in key store Parent picklist value and value store the child picklist value. Now when any user select parent picklist value rerender the section and get value from map and add them in child picklist field.
You can override the standard Edit page to use this functionality. But keep in mind that this is not a fool-proof solution and any user with basic development skills can by pass this approach.
But for security and if your picklist value are fixed you can take help of validation rule to prevent user to enter wrong combination. Something like if(Parent_A includes('parA') and Child_B includes ('test, test2'), false, true)
Update: In this case you can use trigger on before insert, before update so it will look like
if(parent value == 'A')
{
if(child value != 'A' && child value != null) //remove null if you want second picklist required
sob.addError('Wrong value')
}
else if(parent value == 'B')
{
if(child value != 'B' && child value != null) //remove null if you want second picklist required
sob.addError('Wrong value')
}