Eu não sei o que é JPA (eu posso pesquisar no Google; o que quero dizer é que não estou familiarizado com isso); mas:se houver alguma esperança de lidar com uma consulta SQL, e o único problema for traduzir uma condição em tuplas, reescreva a consulta assim:
select city
from user
where firstname = 'a' and lastname = 'b'
or firstname = 'c' and lastname = 'd'
;
Isso é o que o mecanismo de consulta fará com sua consulta original independentemente; você pode olhar para um EXPLAIN PLAN para se convencer disso.
Algumas pessoas gostam de colocar parênteses em torno de cada par de
AND -condições conectadas; Eu não, não mais do que eu usaria parênteses para 2 * 3 + 4 * 6, mas se você sentir que eles adicionam clareza, você pode adicioná-los. 
