A person applies for a job at the XYZ company. The XYZ company is a private company. As part of applying he fills out an application and signs it under penalty of perjury. The application has several lies in it. Can he be criminal prosecuted for perjury? If his signature had been notarized after he signed it, would that effect the answer?
A "penalty of perjury" statement includes not just the warning about penalty of perjury, the person signing avows that the statements are true to the best of their knowledge. If you lie on such a statement, and if the "penalty of perjury" statement is legally allowed (typically, mandated), then the person can be prosecuted. However, XYZ cannot arbitrarily inject the risk of perjury, that requires some legal authorization. An example would be if XYZ is employing the person under a Defense Department contract that requires a sworn statement. The federal perjury statute characterises this as being when "a law of the United States authorizes an oath to be administered". The only effect of notarization is that it decreases the probability that the person could effectively argue "I never even signed this statement, that's a forgery".
It won't be perjury, but (with or without the "under penalty of perjury" phrase) it will be fraud.
Perjury is making a false statement in connection with a judicial proceeding.
You could be asked to sign a Statutory Declaration
Anyone can ask you to sign one of those although it will usually be a state one rather than the Federal one linked to.
Lying on one of those is a criminal offence that carries serious gaol time.
Of course, lying on a job application is technically fraud
Whether you get prosecuted depends on how big the lie is. Run of the mill padding is unlikely to get you in trouble. Saying you’re a surgeon when you aren’t likely will (it has happened).
In Engilsh law, the term 'Perjury' holds a very specific meaning, to wit lying in a legal proceeding where you are under oath to tell the truth.
Perjury Act (1911)
If any person lawfully sworn as a witness or as an interpreter in a judicial proceeding wilfully makes a statement material in that proceeding, which he knows to be false or does not believe to be true, he shall be guilty of perjury
The expression “judicial proceeding” includes a proceeding before any court, tribunal, or person having by law power to hear, receive, and examine evidence on oath.
So no, your actions do not meet the legal requirement for perjury unless your individual has been lawfully sworn as a witness.